Пленарный граф

Cтраница 1

Внешнепланарный граф и две его внешнеплоские укладки.| Три максимальных внешнеплоских графа. [1]

Пленарный граф называется внешнепланарным, если его можно уложить на плоскости так, чтобы все его вершины принадлежали одной грани. Обычно в качестве такой грани мы будем брать внешнюю грань. На рис. 11.5 показан внешнепланарный граф ( а) и две - ( 6) и ( б) - его внешнеплоские укладки. [2]

Любой 5-связный пленарный граф имеет по крайней мере 12 вершин. [3]

Каждый 3-хроматический максимальный пленарный граф однозначно 3-раскрашиваем. [4]

Пленарный граф и его укладка. [5]

Изучение пленарных графов было начато Эйлером в его исследованиях полиэдров. С каждым полиэдром связан граф, состоящий из точек и линий полиэдра; этот граф называется l - скелетом. Например, граф Q3 есть 1-скелет куба, а / С2 2 2 - это 1-скелет октаэдра. [6]

Однозначно 3-ра-скряшиваемый граф, не имеющий треугольников.| Однозначно 3-раскрашиваемый планарный граф. [7]

Однако каждый однозначно 3-раскрашиваемый пленарный граф должен содержать треугольники. [8]

Хотя вопрос существования 5-раскрашиваемых пленарных графов остается все еще открытым, результат Хедетниеми, приведенный в работе Чартрэнда и Геллера [1], разрешает проблему однозначно. [9]

Перекрещивающиеся и неперекрещивающиеся цепи. [10]

Теорема 5.3. Пусть G - пленарный граф, в котором цепи х к у имеют единственную общую вершину - у - Тогда для существования плоского топологического представления ( G), в котором цепи х и у не перекрещиваются в вершине у, необходимо и достаточно, чтобы граф AG был пленарным. [11]

Трудности, возникающие при перечислении пленарных графов, интуитивно объясняются родством этих задач с проблемой четырех красок. Если будут найдены производящие функции для числа пленарных графов и пленарных 4-хроматических графов и будет установлено равенство, то тем самым будет доказано предположение о четырех красках. С другой стороны, если будет показано, что эти числа не совпадают, то предположение о четырех красках будет опровергнуто. [12]

Так как диаграмма Вороного является пленарным графом, то для ее представления достаточно линейного по числу точек объема памяти. Это позволяет представить информацию о близости в чрезвычайно компактной форме. Любой конкретный многоугольник Вороного может иметь до Л7 - 1 ребер, но полное число ребер не превосходит 3N - 6, при этом каждое ребро принадлежит в точности двум многоугольникам. Это значит, что среднее число ребер многоугольника Вороного не превосходит шести. [13]

В главе 1 упоминалось, что пленарный граф всегда может быть уложен на плоскости так, что его ребра перейдут в прямолинейные отрезки. Любой ППЛГ определяет, вообще говоря, подразбиение плоскости; если в ППЛГ нет вершин со степенью 2, то можно непосредственно убедиться в том, что все ограниченные области этого подразбиения - простые многоугольники. Без потери общности здесь и далее граф предполагается связным. [14]

Рассматривайте сеть на рис. 29.7 как пленарный граф G; образуйте двойственный ему граф G и припишите каждому ребру из G ту же пропускную способность, что и у соответствующего ему ребра в G. [15]

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