Плоский граф

Cтраница 4

Плоские колеса.| Две укладки двусвязного графа на плоскости. [46]

Теорема 11.7. Любой планарный граф изоморфен плоскому графу, у которого все ребра являются отрезками прямых. [47]

Так как наибольшим числом ребер в плоском графе обладает граф, у которого каждая грань есть треугольник, то получаем необходимое условие планарности графа в терминах числа ребер. [48]

Если в каждой области, на которые плоский граф делит всю плоскость ( включая и внешнюю область), нарисовать по одной вершине и каждую пару вершин, лежащих в смежных областях, соединить ребром, то получится граф, называемый двойственным к исходному. [49]

Два 4-хроматических пленарных графа. [50]

Финк и Закс [1] доказали, что любой плоский граф, содержащий не более 21 треугольника, 4-раскрашиваем. [51]

Иллюстрации к теореме Поша.| Граф Татта. [52]

Тейт [1] высказал предположение, что каждый трехсвязный плоский граф J) содержит остовный простой цикл. [53]

Иллюстрация основной идеи метода. Триангуляция Э - образуется в результате заворачивания выпуклых оболочек Р и Р %. [54]

Здесь термин грань используется в общепринятом для плоских графов смысле. Однако в оставшейся части этого раздела будет использоваться термин гипергрань, чтобы подчеркнуть, что они являются ( d - 1) - мерными множествами. [55]

Алгоритм особенно эффективен в случае x0z - плоского графа или при малом числе ребер множества Т в общем случае. [56]

Будем говорить, что грани или ребра плоского графа раскрашены правильно, если им поставлены в соответствие цвета таким образом, что нет двух смежных граней ( или ребер), имеющих один и тот же цвет. [57]

Теорема 11.3. Для любой выделенной грани f двусвязного плоского графа G найдется на плоскости изоморфный ему плоский граф, у которого грань, соответствующая грани f, будет внешней. [58]

Страницы: 1 2 3 4