Головна

Повні графи і дерева

  1.  NP-повні задачі
  2.  бінарні дерева
  3.  Бінарні дерева.
  4.  Бінарні дерева.
  5.  гідрографії повінь
  6.  Глава 11. Будинок на деревах
  7.  дерева

Граф називається повним, Якщо будь-які дві його вершини заплющив, тобто мають загальне ребро.

1

 5 2

- До5

       
   


 4 3

 n (n-1)


теорема: У повному графі з n вершинами ребер.

Доведення. Кожна з 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

 




 система Генцен |  система Аристотеля |  Категоричні висловлювання. |  Модальні логіки. |  теорія Автоматів |  приклади автоматів |  виходів |  мінімізація автоматів |  Перехід від автомата Мура до автомату Мілі і навпаки |  теорія графів |

© um.co.ua - учбові матеріали та реферати