Flashcards
8. Планарные графы
Cards in this deck (12)
- 1Планарный графГраф, допускающий такое отображение на плоскости (или сфере), что любые его два ребра могут пересекаться только в точке, обозначающей вершину графа.
- 2Грань плоского графаЛюбая область плоскости, ограниченная рёбрами и вершинами графа.
- 3Степень граниКоличество рёбер, ограничивающих эту грань. Мост даёт +2 к степени грани.
- 4Сумма степеней гранейСумма степеней граней равна удвоенному количество рёбер, так как каждое ребро учитывается в степени двух граней (либо в степени одной, но дважды).
Следовательно, сумма степеней граней равна сумме степеней вершин. - 5Дуальный графГраф, полученный из исходного заменой вершин на грани и граней на вершины. Принцип построения: поставить в центре каждой грани вершину и соединить с вершинами всех смежных граней через каждое разделяющее ребро.
- 6Теорема КуратовскогоЕсли граф содержит двусвязные компоненты, являющиеся подразбиениями K3,3 или K5, то он не планарен, и наоборот - если не содержит, то планарен. Подразбиение - граф, полученный из исходного добавлением вершин посреди рёбер.
- 7Теорема ВагнераГраф является планарным тогда и только тогда, когда графы К3,3 и К5 не являются его минорами. Минор - граф, полученный из исходного удалением либо стягиванием рёбер.
- 8Формула Эйлера для связных планарных графов. СледствиеV - E + F = 2
Поскольку степень любой грани в простом графе больше или равна 3, то следует неравенство E <= 3V-6 - 9Род поверхностиУсловно говоря - количество "ручек" (или "отверстий"), которые имеются у поверхности. Поверхности одинакового рода топологически эквивалентны.
- 10Правильное вложение графа в поверхностьТакое вложение графа в поверхность, при котором, если разрезать поверхность по рёбрам графа, получатся криволинейные n-угольники.
- 11Эйлерова характеристика картыЕсли граф можно правильно вложить в поверхность рода g, то для граф справедливо уравнение:
V - E + F = 2 - 2g - 12Теорема о краскахВершины (или грани) любого планарного графа можно окрасить в 4 цвета.
Information
- Description
- Карточки по 8-й лекции курса "Основы теории графов" на stepic.org
- Created by
- Sergei Fomin
- Views
- 192
- Tags
- Rating