загрузка...
загрузка...
На головну

Лекція № 2. Введення в теорію графів (продовження)

Дивіться також:
  1. I. ВСТУП
  2. I. Вступ
  3. I. Вступ в комп'ютерну графіку.
  4. I. Лекція з історії психології
  5. I. ВСТУП
  6. Primer 2 Лекція 10.
  7. Primer 4 Лекція 10.
  8. БУТТЯ І МАТЕРИЯ Лекція 4
  9. В. І. Вернадський (1863 - 1945) - великий російський і радянський вчений і філософ-косміст. Детально обгрунтував теорію ноосфери.
  10. Вступ
  11. ВСТУП
  12. ВСТУП

Рис 1. Ейлерови і Гамільтона графи.

       
   


Ейлеров і Гамильтонов але не

гамильтонов ейлерів


Ейлеров (Ейлером цикл

),

 але не гамільтонів.

Наведемо Доведення негамільтоновості графа .

вершину назвемо ізольованою елементарним циклом , Якщо він містить ланцюг , Що включає всі суміжні з нею вершини, і не включає саму вершину.

Зауважимо, що у Гамільтона циклу немає ізольованих вершин.

Нехай існує гамільтонів цикл . Можливі такі випадки:

1). . тоді - Ізольована вершина.

2). . тоді - Ізольована вершина.

3). . тоді и - Ізольовані вершини.

Отже, цикл НЕ гамильтонов, і граф також негамільтонов.

визначення 23: Відображення називаетсявзаімнооднозначним, якщо

.

Визначення 24: Взаимнооднозначное відображення безлічі вершин графа на безліч вершин графа і ребер (дуг) на , Що зберігає відношення інцидентності, називається ізоморфізмом графів и :

.

Зауваження. У простому графі досить визначити ізоморфізм на безлічі вершин.

Визначення 25. Граф, ізоморфний частини графа , Називається подграфом .

Рис 2. Подграф.


Визначення 26. Граф називається плоским (планарним), якщо його можна ізоморфно відобразити на граф , Розташований на площині без самоперетинів.

Основні види графів. «-- попередня | наступна --» Доповнення. Дерева.
загрузка...
© om.net.ua