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

Однако, для гамильтоновых графов не удалось доказать красивой теоремы, наподобие
теоремы Эйлера.

                                   4.3. Полные графы и деревья

Граф называется полным, если любые две его вершины смежены, т.е. имеют общее ребро.




                   1

           5                       2
                                       - К5

               4           3

Теорема: В полном графе с n вершинами                   n(n-1)   ребер.
                                                           2
Доказательство. Каждая из n вершин полного графа связана с n-1
. вершинами, то есть n(n-1).
При таком подходе каждое из ребер учитывается дважды, поэтому надо разделить
произведение на два.

   В полном графе всегда существует гамильтонов цикл, и он определяется любой
циклической подстановкой (см. теорию групп).
 Граф G называется дополнением графа G, если их объединение дает полный граф.

   1               2               1            2

                   G                                G


   4               3           4               3


               1                                    1

   5                       2           4                     3
                               G                                 G

       4               3                   2             5


                                               4.4. Деревья

   Дерево - это связный граф без циклов. Можно дать другое определение дерева или
вывести его из первого. Дерево – это граф, между любой парой вершин которого
существует единственная цепь.


                                                    — 51 —