Плоский граф

Cтраница 2

Для случая плоских графов понятие квазиграни совпадает с понятием грани, и формула (5.10) приобретает вид формулы Эйлера. [16]

Способы установления, плоский граф или нет, находят практическое применение к электронным схемам, в частности к печатным схемам и микроминиатюрным интегральным схемам, однако там приходится учитывать и другие факторы: например, иногда имеет значение длина соединительных линий, а в некоторых случаях компоненты схемы могут взаимодействовать, хотя они и не пересекаются. [17]

Многоугольный граф - плоский граф, в котором ветви ( ребра) образуют многоугольники. В пространстве этому графу соответствует одно многоугольное тело. [18]

Прямолинейным графом называется плоский граф, в котором каждое ребро является отрезком прямой линии. [19]

Пусть G - простой плоский граф, имеющий менее двенадцати граней, и предположим, что степень каждой вершины в G не меньше трех. [20]

Теорема 4.10. Каждый обыкновенный плоский граф изоморфен прямолинейному графу. [21]

Если О - максимальный плоский граф, в котором каждый треугольник ограничивает некоторую область, не содержащую ребер, то граф О гамильтонов. [22]

Пусть G - произвольный плоский граф, а Е - ребро G, не являющееся перешейком. [23]

Лемма 4.12. Каждый обыкновенный плоский граф G является подграфом плоской триангуляции с тем же самым числом вершин. [24]

Если каждая грань плоского графа ограничена циклом из трех ребер, то такой граф называется плоской триангуляцией. [25]

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

Области, определяемые плоским графом, назовем его гранями ( или внутренними гранями); неограниченную область будем называть внешней гранью. Если границей грани плоского графа является простой цикл, то иногда под гранью будем понимать этот цикл. Из этих граней только / 2 ограничена простым циклом. [27]

Что можно сказать о плоском графе, который одновременно 2-раскрашиваем и вершинно 2-раскрашиваем. [28]

Обратно, пусть G - кубический плоский граф без мостов, у которого х ( G) 3; раскрасим его ребра с помощью трех ненулевых элементов группы F. Цвет любой другой области R графа G определим следующим образом. R так, что С не проходит через вершины графа G. Цвет области R определяется как сумма цветов ребер, пересекающих кривую С. [29]

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

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