Специальная математика. Соловьев А.Е. - 53 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Составители: 

Рубрика: 

Пример.
2 3 5 5
6
4 4 8 6
6
Жирными линиями выделено минимальное дерево
Теорема Кэли для раскрашенных деревьев.
Для n вершин существует n
n-2
различных помеченных деревьев.
Например, существует 16 различных деревьев с четырьмя вершинами.
1 2 3 4
4 3 2 1
4 вершины 4
4 - 2
= 16 различных помеченных деревьев
1 2 3
4.6. Планарные графы
Граф - плоский, если он изображен на плоскости без пересечения ребер.
Граф - планарный, если он может быть изображен на плоскости без пересечения ребер.
Любой плоский граф может быть преобразован в граф с прямыми ребрами.
неплоский, но плоский плоский с
планарный прямыми ребрами
Граф, где все вершины соприкасаются с внешней гранью - внешнепланарный.
Два "замечательных" непланарных графа:
К
5
К
3,3
Приведем без доказательства две теоремы:
Любой граф, содержащий в качестве подграфа К
5
или К
3,3
- непланарен.
Два графа гомеоморфны если они тождественны с точностью до вершин со степенью =2.
— 53 —
4
Пример.


                      2            3    5        5

                              6

              4           4                          8   6



                                       6

Жирными линиями выделено минимальное дерево
Теорема Кэли для раскрашенных деревьев.
Для n вершин существует nn-2 различных помеченных деревьев.
Например, существует 16 различных деревьев с четырьмя вершинами.
1 2 3 4

4   3     2       1
                                  4 вершины  44 - 2 = 16 различных помеченных деревьев
    1     2       3

                      4
    4.6.                                                     Планарные графы

Граф - плоский, если он изображен на плоскости без пересечения ребер.
Граф - планарный, если он может быть изображен на плоскости без пересечения ребер.
Любой плоский граф может быть преобразован в граф с прямыми ребрами.


                                                        

неплоский, но                          плоский                   плоский с
планарный                                                     прямыми ребрами

Граф, где все вершины соприкасаются с внешней гранью - внешнепланарный.
Два "замечательных" непланарных графа:




                          К5                                  К3,3

Приведем без доказательства две теоремы:
Любой граф, содержащий в качестве подграфа К5 или К3,3 - непланарен.
Два графа гомеоморфны если они тождественны с точностью до вершин со степенью =2.


                                                         — 53 —

Страницы