Cтраница 2
Эта теорема дает нам искомое обоснование использования диаграмм для изображения графов: достаточно взять трехмерное представление и спроектировать его на плоскость так, чтобы никакие две вершины не попадали в одну и ту же точку. Конечно, в общем случае такой метод приводит к пересечениям, хотя в некоторых случаях мы получим диаграммы без пересечений. Произойдет это только тогда, когда рассматриваемый граф может быть уложен на плоскости; такие графы называются планарными графами. Подробнее планарные графы будут изучены в гл. К ним относятся, например, вполне несвязные графы, граф / Си платоновы графы, циклические графы, колеса и звездные графы. [16]
Эта теорема дает нам искомое обоснование использования диаграмм для изображения графов: достаточно взять трехмерное представление и спроектировать его на плоскость так, чтобы никакие две вершины не попадали в одну и ту же точку. Конечно, в общем случае такой метод приводит к пересечениям, хотя в некоторых случаях мы получим диаграммы без пересечений. Произойдет это только тогда, когда рассматриваемый граф может быть уложен на плоскости; такие графы называются планарными графами. Подробнее планарные графы будут изучены в гл. К ним относятся, например, вполне несвязные графы, граф / Си платоновы графы, циклические графы, колеса и звездные графы. [17]
Тогда по теореме 3.3 вершины и и у0 принадлежат различным блокам графа F. Следовательно, в F существует точка сочленения w, принадлежащая каждой простой ( ы - Уо) - цепи. Образуем граф F0, добавляя к F ребра wu0 и wv0, если их еще нет в F. Если, однако, добавление реб-р а дам0 приводит к образованию подграфа Я графа Вь гомеоморфного К. G, который получается заменой ребра wua на простую цепь, идущую из ы0 в а1 и начинающуюся ребром х0, обязательно гомеоморфен графу Я и, значит, гомеоморфен / С5 или / Сз з; мы пришли к противоречию. Поэтому BI и аналогично В2 - планарные графы. [18]