8) Числовые характеристики неориентированных графов. Применение числовых характеристик для оптимизации конструкторских задач проектирования рэс. Понятие внутренне и внешне устойчивых множеств.

Цикломатическое число. При рассмотрении произвольного не­ориентированного графа G(X, U) без петель с \Х\ = п и \U\ = г, состоящего из р компонент связности, величину v(G) =г —n + р называют цикломатическим числом графа. Иногда вводят понятие ранга графа R(G) = п —р. В этом случае цикломатическое число v (G) = r — R(G).

Цикломатическое число графа указывает то наименьшее число ребер, которое необходимо удалить из данного графа, чтобы получить дерево (для связного графа) или лес (для несвязного графа), т. е. добиться отсутствия у графа циклов. Цикломатическое число всегда неотрицательно.

Хроматическое число графа — минимальное число k, такое что множество вершин графа можно разбить на k непересекающихся классов :

таких, что вершины в каждом классе независимы, то есть любое ребро графа не соединяет вершины одного и того же класса.

Если в графе G(X, и) имеется не­которое подмножество вершин R принадлежащее X, не смежных остальным вер­шинам графа, то такое подмножество называют внешне устойчивым. Величину, равную мощности внеш­не устойчивого подмножества, содержащего наименьшее число эле­ментов, называют числом внешней устойчивости

Если в графе G(X_,U) имеется некоторое подмножество F_t принадлежащее X несмежных между собой вершин, то такое подмножество F_t называют внутренне устойчи­вым.

Величину, равную мощности наибольшего внутренне устойчивого подмножества, называют числом внут­ренней устойчивости графа

9) Алгоритм выделения внутренне устойчивых множеств графов (алгоритм Магу).

Изложенный метод Ж- Магу для выделения всех непополнимых внутренне устойчивых подмножеств позволяет найти и минималь­ную раскраску графа [10]. Для этого строят матрицу , где п = |Х|; т = каждый элемент которой

В нашем случае

Поставим в соответствие каждой вершине графа G(X, U) сумму тех в которые она входит, и запишем произведение этих сумм:

Раскрыв скобки по правилам булевой алгебры, получим:

Каждое из слагаемых содержит в неявном виде все вершины гра­фа G(X, V). Поэтому для нахождения всевозможных минимальных раскрасок оставим в произведении Пv только слагаемые, содержа­щие минимальное число сомножителей F_} (в нашем случае первые пять), и, раскрыв их, устраним всеми возможными способами дублирующие вершины. В общем случае каждое слагаемое дает 2k вариантов рас­краски, где k — число дублирующих вершин в сомножителях слагае­мого. Например, пятое слагаемое дает четыре варианта хроматиче­ской раскраски графа при k —2 (табл. 2.1).

Знание числа внутренней устойчивости графа оказывается полез­ным при размещении компонентов на коммутационной плате, связан­ным с итеративными операциями перестановки компонентов (вершин графа), когда в качестве основного критерия оптимальности решения используют минимум суммарной длины связей между компонентами.