Изменения

Перейти к: навигация, поиск

Двойственный граф планарного графа

662 байта убрано, 05:25, 17 ноября 2010
фикс
«…Для Чтобы для данного плоского графа ''G'' его построить двойственный ''G&prime;'', необходимо поместить по вершине ''двойственный граф G&prime; ''строится следующим образом: поместим в каждую область грань ''G'' (включая внешнюю) по одной вершине графа , а затем, если две грани в ''G&prime;'' и, если две области имеют общее ребро ''x'', соединим помещенные соединить ребром соответствующие им вершины в них вершины ребром ''xG&prime;''(если грани имеют несколько общих рёбер, пересекающим только ''x''соответствующие вершины следует соединить несколькими параллельными рёбрами). В результате всегда получится плоский псевдограф. Ясно, что ''G&prime;'' имеет петлю тогда и только тогда, когда в ''G'' есть концевая вершина; ''G&prime;'' имеет кратные рёбра тогда и только тогда, когда две области графа ''G'' содержат по крайней мере два общих ребра. Таким образом, двусвязный плоский граф имеет всегда в качестве двойственного или граф или мультиграф, в то время как двойственный граф трёхсвязного плоского графа всегда представляет собой граф. Другими примерами двойственных графов являются платоновы графы Например: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр…»<ref>икосаэдр. Эти пять графов, образованные вершинами и рёбрами правильных многогранников, называют ''Харари, Ф.платоновыми'' Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009. — С. 138. — ISBN 978­-5­-397­-00622­-4.</ref>.

Навигация