Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

Симметризация орграфа

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

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

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

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

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

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

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы