Глоссарий к главе 3

Внешне устойчивое подмножество – это подмножество, вершин графа, которые являются смежными со всеми остальными вершинами графа. Внешне устойчивое подмножество называется минимальным, если удаление из него произвольной вершины делает его внешне неустойчивым.

Внутренне устойчивое подмножество графа – это подмножество любые две вершины, которого являются не смежными.

Гиперграф Н = (Х, Е) – это объект, который состоит из множества вершин X и множества ребер E, причем каждое ребро l_i  E представляет собой некоторое подмножество множества вершин, т.е. l_i  X.

Области, определяемые плоским графом, называются его внутренними гранями или просто гранями. Неограниченная область называется внешней гранью.

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

Гиперграф H* называется двойственным гиперграфу H = (X, E), если, вершинами H* являются ребра H, а ребрами – вершины H.

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

Гиперграф Н= (X, Е) можно представить в виде двудольного графа Кёнига К(Н) = (X  E, V), где X – первое подмножество вершин двудольного графа, соответствующее множеству вершин гиперграфа H; Е – второе подмножество вершин двудольного графа, соответствующее множеству ребер гиперграфа H; V – множество ребер двудольного графа, устанавливающее смежность между двумя множествами вершин X и Е в графе К(Н) в соответствии с инцидентностью вершин и ребер гиперграфа H.

Гиперграф H = (Х, Е) считается деревом в случае, когда его ребра имеют не более одной общей вершины.

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

Максимальное внутренне устойчивое подмножество (МВУП) или независимое (НП) подмножество – это подмножество графа такое, что добавление к нему любой новой вершины делает его внутренне неустойчивым.

Максимально планарный граф – это граф, который при добавлении любого ребра перестает быть планарным.

Планарный граф – это граф, который можно уложить на плоскости так, что никакие два его ребра не будут иметь пересечений. Плоский граф – это граф, уже уложенный на плоскости.

Плоской картой называется связный плоский граф вместе со всеми его гранями.

Граф называется полным двудольным, если любая его вершина, принадлежащая одному подмножеству, смежна с каждой вершиной другого подмножества и наоборот.

Понтрягина - Куратовского теорема: граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного графам K₅ или K_3,3.

Предельные подмножества – это независимые подмножества, содержащие наибольшее число элементов.

Раскраска вершин графа – это разбиение множества вершин на k непересекающихся классов (подмножеств) таких, что внутри каждого подмножества не должно содержаться смежных вершин.

Под раскраской вершин гиперграфа Н = (Х, Е) понимается некоторое разбиение множества его вершин на классы, не содержащие пустого подмножества, когда инцидентные вершины должны быть окрашены в разные цвета, причем каждому классу назначается определенный цвет, в который окрашены вершины, а величина q соответствует количеству различных цветов, которые можно использовать для раскраски.

Граф G называется стягиваемым к графу Н, если граф Н можно получить из графа G с помощью некоторой последовательности элементарных стягиваний.

В гиперграфе H = (X, E) две вершины называются смежными в том случае, если существует ребро, содержащие эти вершины.

Ребра гиперграфа называются смежными в случае если их пересечение представляет собой непустое подмножество

Толщина графа – наименьшее число планарных подграфов, объединение которых дает исходный граф.

Фундаментальные циклы – это циклы, получаемые добавлением какого-нибудь ребра из графа к ребрам дерева и отличающиеся один от другого хотя бы одним ребром.

Харари – Татта теорема: граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в K₅ или K_3,3.

Хроматическое число графа (G) – наименьшее число подмножеств, на которое разбивается граф при раскраске.

В гиперграфе Н = (Х, Е) цепь длины q определяется как последовательность вида s(H) = x₁, l₁, х₂, 1₂, …, l_q, x_q+1.

Цикломатическое число графа – это наименьшее число ребер, которые необходимо удалить из графа, чтобы он стал ациклическим (деревом). Цикломатическое число определяется по формуле: (G) = m – n + k, где n – число вершин, m – число ребер, k – число компонент связности графа.

Число внутренней устойчивости графа определяется мощностью предельного независимого подмножества.

Число внешней устойчивости графа определяется мощностью минимального внешне устойчивого подмножества, содержащего наименьшее число вершин.

Число скрещиваний (пересечений) графа – наименьшее число пересечений ребер, которое получается при расположении графа на плоскости.

Ядро графа – это некоторое подмножество вершин графа, являющееся одновременно внутренне и внешне устойчивым.