4481537
Description
Flashcards by Sergei Fomin, updated more than 1 year ago
|
Created by Sergei Fomin
almost 9 years ago
|
|
| 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 цвета. |
Want to create your own Flashcards for free with GoConqr? Learn more.