8. Планарные графы

Sergei Fomin
Flashcards by , created over 3 years ago

Карточки по 8-й лекции курса "Основы теории графов" на stepic.org

8
0
0
Sergei Fomin
Created by Sergei Fomin over 3 years ago
Доли и дроби
Татьяна Иващенко
Събиране и изваждане до 6
Светла Събева
7. Раскраска графов
Sergei Fomin
An-tAdh le Padraig o Conaire
l.watters97
Media Studies Quiz
Amanda Louise Lord
6. Паросочетания в графах (ч. 2)
Sergei Fomin
2. Циклы в графах
Sergei Fomin
1. Основные понятия теории графов
Sergei Fomin
3. Связность в графах
Sergei Fomin
4. Связность в графах (ч. 2)
Sergei Fomin
Question Answer
Планарный граф Граф, допускающий такое отображение на плоскости (или сфере), что любые его два ребра могут пересекаться только в точке, обозначающей вершину графа.
Грань плоского графа Любая область плоскости, ограниченная рёбрами и вершинами графа.
Степень грани Количество рёбер, ограничивающих эту грань. Мост даёт +2 к степени грани.
Сумма степеней граней Сумма степеней граней равна удвоенному количество рёбер, так как каждое ребро учитывается в степени двух граней (либо в степени одной, но дважды). Следовательно, сумма степеней граней равна сумме степеней вершин.
Дуальный граф Граф, полученный из исходного заменой вершин на грани и граней на вершины. Принцип построения: поставить в центре каждой грани вершину и соединить с вершинами всех смежных граней через каждое разделяющее ребро.
Теорема Куратовского Если граф содержит двусвязные компоненты, являющиеся подразбиениями K3,3 или K5, то он не планарен, и наоборот - если не содержит, то планарен. Подразбиение - граф, полученный из исходного добавлением вершин посреди рёбер.
Теорема Вагнера Граф является планарным тогда и только тогда, когда графы К3,3 и К5 не являются его минорами. Минор - граф, полученный из исходного удалением либо стягиванием рёбер.
Формула Эйлера для связных планарных графов. Следствие V - E + F = 2 Поскольку степень любой грани в простом графе больше или равна 3, то следует неравенство E <= 3V-6
Род поверхности Условно говоря - количество "ручек" (или "отверстий"), которые имеются у поверхности. Поверхности одинакового рода топологически эквивалентны.
Правильное вложение графа в поверхность Такое вложение графа в поверхность, при котором, если разрезать поверхность по рёбрам графа, получатся криволинейные n-угольники.
Эйлерова характеристика карты Если граф можно правильно вложить в поверхность рода g, то для граф справедливо уравнение: V - E + F = 2 - 2g
Теорема о красках Вершины (или грани) любого планарного графа можно окрасить в 4 цвета.