Плоский граф

Cтраница 1

Плоский граф, изображенный па рис. 3.6, соответствует вершинам и ребрам двенадцатигранника ( последний содержит 20 вершин и 12 пятиугольных граней. [1]

Плоский граф двусвязен тогда и только тогда, когда геометрически двойственный к нему граф двусвязен. [2]

Плоский граф - конечное множество простых топологически замкнутых линий, называемых ребрами, на 2-сфере, таких, что любая точка пересечения двух различных элементов этого множества является концом каждого из этих элементов. [3]

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

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

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

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

Для плоских графов задача перечисления разрезов эквивалентна задаче перечисления циклов двойственного графа. [8]

Ребра плоских графов рисуются как кривые, а их грани-как многоугольники, заполненные цветом или штриховкой. Функции двух переменных могут быть изображены всеми теми способами, которые разработаны для этого в научной графике. [9]

Для плоских графов, в которых всякое ребро является перешейком, теорема 1 не имеет смысла. Удобней сказать, что она тривиально выполняется для таких плоских графов. [10]

Для данного плоского графа G построим сейчас другой граф G, называемый ( геометрически) двойственным к G. Иллюстрацией этой процедуры служит рис. 15.1, где вершины vt изображены крестиками, ребра е графа G - сплошными линиями, а ребра е графа G - пунктирными. [11]

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

Попытайтесь найти плоский граф с пятью гранями, обладающий тем свойством, что любые две его грани имеют общее ребро. [13]

Если такой плоский граф имеет 5 или более вершин, то в силу (3.4) он не является 4-связным. [14]

У каждого плоского графа обязательно имеется одна бесконечная грань, не ограниченная ребрами. [15]

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