Полный подграф

Cтраница 4

Граф G является реберным графом некоторого графа тогда и только тогда, когда граф G может быть описан как такое объединение полных подграфов, что ни одна вершина из G не принадлежит более чем двум из этих полных подграфов. [46]

Повторяя названную процедуру, в конечном итоге мы получим граф, вершины которого имеют вид ABC... ZQ обозначает полный подграф исходного графа. [47]

Порожденный подграф называется полным, если все его вершины попарно смежны. Число вершин полного подграфа называется его степенью. [48]

Наибольшим полным подграфом называется полный подграф, содержащий наибольшее число вершин среди всех полных подграфов данного графа. Число вершин наибольшего полного подграфа, содержащегося в данном графе, называется плотностью этого Графа. Плотность графа будем обозначать как f ( F) или / в тех случая х, когда будет ясно, о каком графе идет речь. [49]

Граф, в котором каждые две вершины смежные, называется полным; полный граф, имеющий п вершин, обозначается через Кп. Максимальный по включению полный подграф графа G называется кликой в G. Подграф Н называется исключительным относительно некоторого свойства PROP, если ни один граф со свойством PROP не имеет Н своим подграфом. [50]

Рассмотрим некоторое ( желательно близкое к наименьшему) покрытие графа полными подграфами. Граф полностью определится указанием этих полных подграфов и ребрами, которые соединяют вершины разных подграфов. Yn сопоставлено полным подграфам. [51]

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

Каждой вершине ( букве) сопоставим множество идентификаторов, в которые эта буква входит. Тогда всякому слову взаимно однозначно соответствует полный подграф, каждой вершине которого соответствует идентификатор этого слова. Полный подграф, соответствующий слову, будем называть элементным. Две вершины и и - соединены ребром, если им соответствует хотя бы один общий идентификатор. [53]

Граф и его клики. [54]

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

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