Теория графов и комбинаторика

на сфере, к обратно. Это легко доказать, пользуясь отах)0огра1п- ческой проекцией. Не всякий граф можаг йнть уложен на плоокос ч , I'lH-jepooe. вопрос о минимальной размерности проотранотва, в котором укла­ дывается любой граф. Теорема I I . 4 . Любой граф можно уложить в трехмерном енкл::- •донс проотранотве. Докдза'гбдьотво. П УСТЬ Б* - ( р Д ) -граф. Выберем произвольную прямую Zi в . В'"т>шинн графа" изобразим различншли точками щда- K- i L , Проведом чере з L пучок из плоокоотей. Зтим roioc- к о с т ш поставим во взаимно-одиозпачное ооответотвиа рабра I'pa;]^. Казэдоа ребро изображается а '^-'оай плоокости. Петля графа изоб­ ражается окружностью, проходящей через , зответотвумцую варш^.^ ; ребра, совданящие разные веришны, изображаем полуокружно'^'1'ью, проходящей ч е р е з эти нвриш £ ш. Яоно, что так будет получена ук­ ладка графа <г . , Эта теорема / "вт обоснование ионольэования диаграмм графов. Для получения диаграммы надо взять трвх>лврнов пр0дотавлеш1е и опроектиропатъ его на плоскость так, чтобы проекции разных вер­ шин н е оовпадали. R общем случае поотрс^.шая таким образом диа­ грамма будет иметь иервоечания. Диаграмма без ПР ; ЧО0 Ч0 НИЙ МОЖДТ быть получена только тогда, когда граф пленарный. Основными планаршши графами являются и Докажем, ч т о граф 1^5 не п'^нарный. Допустим, что - планарный. Изо­ бразим HMe »f*nHftoa в простой цикл Z ® (tT, ) даинн 5 Б ззиде правильного пятиугольника (риоЛХ.Х). Ребро должно целиком находиться либо внутри, либо снаружи 2 • Допустим, что оно находится внутри Е . Ребра и не должны пересекать ребро Поэтому снй должны находиться вне Ч (рИ0Л1.2). Ребро (гГа,1Гу1 не может пересечь и поэтому должно находаться внутри пятиуголъ- , Ри оЛ1Л РиоЛ1.2 ш т а . Аналогично и ребро 1^1, } должно ааходатьо^ внутри пятиуголь" ника. Но в таком случав ребра иерооекутоя. Получено .ротйворечаа, иа которого следует неаланарнссть гра^д К у . Аналогично докааыааетйя явпланарнооть .