Суграф

Cтраница 1

Граф ( а и его фундаментальные деревья ( б, в. [1]

Суграф - часть графа, образованная удалением из исходного графа некоторых ребер. Количество вершин графа и сугра-фа одинаково. [2]

Понятие суграфа включает топологические разновидности графа, которые строятся на отдельных этапах решения данной задачи. [3]

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

Для получения последующих плоских суграфов исследуется суграф Н - G H. [5]

Другими словами, суграф образуется из графа G удалением некоторых ребер. X и F x Fx П X, или, иначе говоря, подграф образуется из графа G удалением некоторых вершин, причем все ребра, инцидентные этим вершинам, также удаляются. [6]

Теорема 18.2.2. Любой покрывающий суграф содержит минимальный покрывающий суграф. [7]

Пусть Н - минимальный покрывающий суграф для G; согласно теореме 13.2.1, Н является суммой частей звездных графов. [8]

Поэтому он также имеет однородный суграф УТ / 2 степени 1, ребра которого можно удалять. [9]

Поэтому он также имеет однородный суграф Mz степени 1, ребра которого можно удалять. [10]

Пусть / / - минимальный покрывающий суграф для G; согласно теореме 13.2.1, Н является суммой частей звездных графов. [11]

Множество з ( М) суграфов произвольного непустого графа М по операциям объединения, пересечения и дополнения по отображению является булевой структурой 23 или булевой алгеброй, которая изоморфна некоторой булевой структуре множеств. [12]

Для получения последующих плоских суграфов исследуется суграф Н - G H. [13]

Суграф графа G ( а и дополнение графа G до полного ( б. [14]

На рис. 4.20, а показан суграф графа, изображенного на рис. 4.19. На рис. 4.20, б приведено дополнение его до полного. [15]

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