На головну

 ОСНОВНІ ПОНЯТТЯ |  ВИЗНАЧЕННЯ |  матриці суміжності |  матриці інціденцій |  списки суміжності |  B f c b d e d b f d |  ТЕОРЕМА 5.3 |  ВИЗНАЧЕННЯ |  ВИЗНАЧЕННЯ |  ВИЗНАЧЕННЯ |

Доведення

  1.  Нескінченно малі функції. Арифметичні дії з нескінченно малими (доказ)
  2.  Другий чудовий межа (доказ)
  3.  Глава 4. Соціальне доказ
  4.  Глава 4. Соціальне доказ.
  5.  Глава 4. Соціальне доказ. Істина - це ми
  6.  Доведення
  7.  Доведення

Покажемо, що K3,3 - Це непланарний граф.

Припустимо гидке. Візьмемо довільну геометричну реалізацію цього графа на площині.

Розглянемо послідовне проходження вершин K3,3 в наступному порядку: a - 2 - b - 3 - c - 1 - a. В даному геометричному поданні K3,3 на площині цього проходженню відповідає переміщення по деякій замкнутій лінії, яка не має самоперетинів.

Ця лінія містить всі вершини графа і 6 ребер, а також ділить площину на дві частини: внутрішню, обмежену замкнутою лінією, і зовнішню. У загальному вигляді виникає ситуація представлена ??на рис. 5.7:

a 2

B

C 3

Мал. 5.7

У внутрішній і зовнішній областях повинні бути зображені 3 ребра (які позначені на малюнку пунктирними лініями). Тому хоча б в одній з цих областей необхідно провести не менше двох ребер. Неважко перевірити, що у внутрішній області неможливо провести більш одного ребра так, щоб відповідні дуги не перетиналися. Розглянемо випадок, коли у внутрішній області зображується ребро (a, 3). Тоді ребра (b, 1) і (c, 1) повинні зображуватися дугами у зовнішній області. Але при будь-якому зображенні ребра (b, 1) кінці останнього ребра (c, 1) неможливо з'єднати без перетину вже проведених ліній. Це так оскільки завжди знайдеться така замкнута область на площині, утворена лініями, які зображують ребра, що одна з вершин c і 1 міститься всередині, а інша зовні цій галузі.

Тому припущення про існування геометричної реалізації графа K3,3 є невірним.

Непланарность графа A5 доводиться аналогічно до наведеного доказу непланарності графаK3,3.

доказ закінчено.

У певному сенсі графи K3,3 и A5 є канонічними непланарнимі графами. Виявляється, що всі інші непланарние графи містять в собі фрагменти, подібні або графу K3,3, або графу A5.

Для того щоб сформулювати критерій планарності графів, визначимо додаткові поняття.

 



 ВИЗНАЧЕННЯ |  ВИЗНАЧЕННЯ
© um.co.ua - учбові матеріали та реферати