Произвольный граф

Cтраница 4

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

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

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

Лемма об эстафете утверждает, что сумма степеней вершин произвольного графа G - ( V, Е) равна удвоенному числу его ребер. [49]

Число Ап простых связных фигур площади п. [50]

Теорема Оттера [46] для деревьев была обобшена Норманом [43] для произвольных графов. Это предложение играет роль полезной комбинаторной леммы в решении некоторых задач перечисления графов. Недавно Рид [51] усовершенствовал свою теорему о суперпозициях для перечисления определенного класса графов общего вида. В целях исторической справедливости заметим, что перечисляющая теорема Пойа и несколько других относящихся к ней приемов подсчета были предвосхищены Ред-филдом в прекрасной статье [56], которая в основном осталась незамеченной. [51]

Затем метод обобщается с целью получения верхних границ для емкости произвольного графа. Вводится детально исследованная и в известном смысле просто вычисляемая функция, которая является верхней границей емкости и во многих случаях равна ей. [52]

Рассмотрим на примере использование предложенного метода минимизации числа пересечений ребер произвольных графов. [53]

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