Симметризация орграфа. 
Геометрическая теория графов

Каждому орграфу G можно поставить в соответствие единственный неориентированный граф G_s, называемый симметризацией орграфа G, если каждую дугу в G, ведущую из одной вершины в другую, заменить неориентированным ребром, соединяющим ту же пару вершин. Так, например, орграфу, изображенному на рис. 178, соответствует симметризация (т.е. неориентированный граф), изображенная на рис. 179. Орграф и его симметризация имеют одинаковое количество элементов.

Дадим более точно определение симметризации. Пусть G (V, E, f) — ориентированный граф, /• Е —> VxV — отображение инциденции. Рассмотрим отображение симметризации s: VxV—) V&V из множества упорядоченных пар VxV множества V на множество неупорядоченных пар V&V множества V, определяемое по закону (А, В) —-—> (А& В). Отображение симметризации каждой упорядоченной паре элементов ставит в соответствие неупорядоченную пару, состоящую из тех же элементов. Тогда отображение.

являющееся композицией отображений / и s, есть отображение из? в V&V. Следовательно корректно определен неориентированный граф G_s(V, E, f_s) со множеством вершин V, множеством ребер Е и отображением инциденции /,. Этот граф называется симметризацией орграфа G (V, E, f).

Дуги исходного орграфа G интерпретировали несимметричные связи во множестве вершин V. В отличие от этого, симметризация G_s имеет столько же ребер, сколько дуг в исходном орграфе G, и ребра в G, интерпретируют теперь симметричные связи между теми же парами вершин.

Разным орграфам может соответствовать одна и та же симметризация. Так, например, расставив произвольным образом стрелки на каждом ребре неориентированного графа (т.е. определив ориентацию каждого ребра), мы превратим ребра в дуги, а исходный граф превратится в орграф, симметризация которого совпадет с исходным графом. Процесс перехода от неориентированного графа к орграфу, симметризация которого совпадает с исходным графом, называется ориентацией графа.

Так как каждая петля может быть ориентирована единственным образом, а каждое ребро, не являющееся петлей, можно ориентировать двумя способами, то мы можем подсчитать количество всех возможных ориентаций конечного графа. Пусть конечный неориентированный граф G имеет п ребер, не являющихся петлями, тогда число всех возможных ориентаций графа G равно 2^я. Для всех этих 2^я орграфов их симметризации будут совпадать. Так, например, граф на рис. 178 имеет 10 ребер, не являющихся петлями. Поэтому его можно ориентировать 2¹⁰=Ю24 различными способами, т. е. этот граф будет являться симметризацией для 1024 орграфов.