Элементарные орграфы. 
Геометрическая теория графов

Ориентированный граф G называется элементарным, если он не содержит петель и строго параллельных дуг. Пример элементарного орграфа изображен на рисунке 182.

Элементарный орграф G может содержать не строго параллельные дуги, поэтому соответствующий неориентированный граф G_s, являющийся его симметризацией, может не быть элементарным графом (в нем могут появиться параллельные ребра). Так симметризацией элементарного орграфа, представленного на рис. 182, является неэлементарный граф (см. рис. 183).

Ориентированный граф G называется элементарным орграфом с петлями, если он не содержит параллельных петель и строго параллельных дуг. В таких графах в каждой вершине может существовать не более одной петли.

Элементарные орграфы с петлями могут быть определены без использования отображения инциденции: элементарным орграфом G (V, E) с петлями называется совокупность непустого множества V (множество вершин) и множества Е (множество ребер), являющегося произвольным подмножеством во множестве Vx V.

Пусть ориентированный граф G (V, E) имеет |У|=л вершин, тогда, если G — элементарный орграф с петлями, то |?|<|Vx V=n², если же G — элементарный орграф, то |?|<�и²-и.

Орграф называется полным, если он не имеет петель и из любой его вершины в любую другую вершину ведет единственная дуга. Ясно, что полный орграф является элементарным и количество его дуг равно п²-п (п — количество вершин).

Ориентированный граф называется полным орграфом с петлями, если из любой его вершины в любую другую вершину ведет единственная дуга и в каждой его вершине существует единственная петля. Ясно, что такой граф является элементарным орграфом с петлями и количество его дуг равно п² (п — количество вершин).