На главную   ::   Содержание



Характеристические числа графа (внутренней, внешней устойчивости, хроматическое, кликовое)

Определение 1.   Графом $ G=<V,E,f>$ называется совокупность двух множеств и отображения $ f:  E\to V\times V$, $ V\neq \varnothing$ называется множеством вершин, $ E$ -- множеством ребер.

Если элементы множества $ E$ мы представляем как упорядоченные пары, то граф называется ориентированным (тогда элементы называются дугами). Если дуги могут быть кратными, то граф называется мультиграфом.

Определение 2.   Набор элементов $ v_0,e_1,v_1,\dots,v_k$, где $ v_i\in V, e_j\in
E$, называется маршрутом, если любые два соседних элемента инцидентны. Если все ребра различны, то маршрут называется цепью. Для неориентированного графа это -- путь. Замкнутая цепь называется циклом.

Определение 3.   $ M\subseteq V$ называется множеством внутренней устойчивости, если все вершины из $ M$ не смежны между собой. Мощность наибольшего множества внутренней устойчивости называется числом внутренней устойчивости $ \alpha(G)$.

Определение 4.   Множеством внешней устойчивости называется множество вершин, инцидентных всем дугам. Число внешней устойчивости -- мощность наибольшего множества внешней устойчивости.

Определение 5.   Клика -- полный подграф исходного графа. Максимальный размер клики -- кликовое число $ \rho(G)$.

Определение 6.   Раскраска графа -- функция $ V\to N$ такая, что $ f(u)\neq f(v)$ для смежных $ u,v$. Хроматическим числом $ \eta(G)$ называется минимальная мощность множества $ \{f(u):  u\in V\}$.

Укажем некоторые соотношения между характеристическими числами графа.

Можно также рассматривать хроматическую функцию графа $ P_G(k)$ -- число способов покрасить граф $ G$ при помощи $ k$ красок. Тогда хроматическое число можно определить как $ \min \{k:  P_G(k)>0\}$

На главную   ::   Содержание