Фундаментальные разрезы

Сетью называется связный орграф G = (M, R) без петель.

Потоком в сети G называется функция: R —> Z, которая ставит в соответствие дуге некоторое число — вес дуги.

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

Пусть G = (М,R) – неорграф, M = {М₁,М₂} - разбиение множества М. Разрезом графа G (по разбиению M) называется множество всех ребер, соединяющих вершины из M₁ с вершинами из M₂.

В связном графе любой разрез непуст.

Непустой разрез К неорграфа G называется простым разрезом или коциклом, если любое непустое собственное подмножество К' множества К не является разрезом ни по какому разбиению.

Другими словами, из К нельзя удалить ни одно ребро с тем, чтобы полученное множество было непустым разрезом.

Теорема. В конечном неорграфе G = (М, R), имеющем с компонент связности, множество ребер К тогда и только тогда является коциклом, когда граф (M,R\K) имеет (с + 1) компонент связности.

Фундаментальный разрез – множество ребёр, которые образуют простой разрез и в который входит только одна ветвь u_i.

Мощность фундаментального множества коциклов не зависит от выбора остова Т и равна корангу v*(G) = n - с.

Аналогично фундаментальным циклам фундаментальному разрезу K_i ставится в соответствие вектор b_i=(b_i1,…,b_im) определяемый по правилу

Множество всех векторов определяет фундаментальную матрицу разрезов.

Пример:Найдем матрицу фундаментальных разрезов графа G = (M,R), изображенного на рисунке.

Поскольку v*(G)= 6 - 1 = 5, имеется пять фундаментальных разрезов.

Ребру 4 соответствует коцикл К₁={1,4}, т.к. при удалении ребра 4 из остова Т множество вершин М разбивается на две части: {а₁}, М/{а₁}, а ребра 1 и 4 образуют разрез по разбиению {{а₁},М/{а₁}}.

Аналогично ребру 5 соответствует коцикл К₂={5}, ребру 6 - коцикл К₃= {1,2,3,6}, ребру 7 – коцикл К₄ = {2,3,7}, ребру 8 – коцикл К₅ ={3,8}.

Следовательно, матрица фундаментальных разрезов имеет вид:

[подсказка: в каждом коцикле должна быть одна ветка и/или несколько хорд]

Планарные графы

Плоским называется граф, вершины которого являются точками плоскости, а ребра — непрерывными плоскими линиями без самопересечений, причем никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины.

Любой граф, изоморфный плоскому графу, называется планарным.

Всякий подграф планарного графа планарен.

Граф планарен тогда и только тогда, когда каждая связная компонента этого графа — планарный граф.

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

Границей графа называется множество вершин и ребер, принадлежащих этой грани.

Пусть n, m, f — соответственно число вершин, ребер и граней планарного графа.

Теорема Эйлера. Для всякого связного планарного графа верно равенство:

n-m+f = 2.

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

Пример: на рисунке изображены исходный граф G и два гомеоморфных графа G₁ и G₂.

Теорема Понтрягина —Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных К₅ или К₃.

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

sk(G) = C_n² – 3n + 6, n≥3

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

Толщина графа равна минимальному числу плоскостей t, при котором граф G разбивается на плоские части G₁, G₂, …, G_i.

Для толщины связного (n, m) графа справедливо:

[…] – целая часть числа;

]…[ = […] + 1;

Булевы функции. Основные понятия

Функцию f, принимающую одно из двух значений, 0 или 1, от n переменных, каждая из которых принимает одно из двух значений, 0 или 1, будем называть булевойфункцией f(x₁,x₂,…, x_n) от n переменных.

Иначе говоря, булевой называется функция вида:

f: {0,1}ⁿ→ {0,1}, где {0,1} – множество.

Множество булевых функций от n переменных будем обозначать .

Любая булева функция может быть представлена в виде таблицы истинности.

Если значение функции f зависит от n переменных то таблица истинности содержит 2ⁿ строк, соответствующих всем различным комбинациям значений этих переменных.

Число булевых функций от n переменных равно числу столбцов, которые можно сопоставить строкам таблиц истинности и равно , т.е. = (мощность).