Плоский граф

Cтраница 3

Теорема 12.19. Пусть G есть 3-хроматический плоский граф. Тт, то G - однозначно 3-раскрашиваемый граф. [31]

Доказать, что вершины всякого плоского графа ( без петель и кратных ребер) можно правильно окрасить в q 6 цветов. [32]

Область плоскости, ограниченная ребрами плоского графа и не содержащая внутри себя ни вершин, ни ребер, называется гранью. [33]

Вернемся теперь к вопросу определения плоских графов и приведем основные сведения, необходимые для доказательства теоремы Понтрягина - Куратовского. [34]

Построение по исходному графу ( а дуального графа ( б. [35]

Приведенное правило применимо только для плоских графов. [36]

Область плоскости, ограниченная ребрами плоского графа, внутри которой нет вершин ребер, называют гранью. Ребра грани образуют простой цикл. Заметим, что плоский граф имеет всегда одну бесконечную грань, не ограниченную ребрами. [37]

Обозначим через X класс всех плоских графов, для которых теорема 1 верна. [38]

Область плоскости, ограниченная ребрами плоского графа и не содержащая внутри себя ни вершин, ни ребер, называется гранью. [39]

Лемма 4.15. Каждая плоская триангуляция обыкновенно плоского графа изоморфна прямолинейному графу. [40]

Задача о максимальном разрезе в плоском графе состоит в следующем. [41]

Эйлеровы и гамильтоновы графы. [42]

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

Максимальное хроматическое число равно 5 для плоского графа. В зависимости от значения к графы именуют х-хроматическими. Над графами могут быть произведены операции расширения в надграф - внедрение некоторых новых вершин в соответствующие ребра, так чтобы эти ребра превратились в цепь, а также сжатия - удаление некоторых вершин и ребер, переводящее граф в другой граф ( подграф), содержащий меньшее их количество. [44]

Доказать или опровергнуть: базис циклов плоского графа, состоящий из границ внутренних областей, всегда получается из дерева. [45]

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