Конъюнктивная форма формула, записанная в виде конъюнкции каких-либо выражений

Теория графов

Граф – множество точек, соединенных определенным образом линиями.

Кратные рёбра – ребра, соединяющие одни и те же вершины
Петля – ребро, соединяющее вершину саму с собой.
Изолированная вершина – вершина, из которой не выходит не одного ребра и у которой нет петель
Смежные вершины – две вершины одного графа, соединенные ребром.
Псевдограф – граф, в котором есть петли или кратные ребра
мультиграф – пвседограф без петель
Подграф – граф, получившийся из исходного путем удаления одной или нескольких вершин и ведущих к ним ребер
Пустой граф- подграф, получающийся из исходного путем удаления всех вершин и ребер
Собственный подграф – непустой подграф, не совпадающий с исходным графом
Надграф – граф, получающийся из исходного путем добавления одной или нескольких вершин в исходный граф
Частичный граф – граф, получающийся из исходного путем удаления одного или нескольких ребер
нуль-граф – граф, получающийся из исходного путем удаления всех ребер
Инцидентность вершины и ребра – вершина являющийся концом ребра
Степень вершины – число ребер, инцидентных данной(висячей) вершине
Висячая вершина – пс. Из которой идет только одно ребро
Однородный̆ - граф, в котором степени всех вершин равны между собой
полный граф – однородный граф без петель в котором каждая пара вершин соединена одним ребром
Изоморфизм графов
Маршрут – непустая последовательность k ребер и k+1 вершина вида
/ цепь/ - маршрут, в котором нет повторяющихся ребер.
простая цепь – цепь, в которой нет повторяющихся вершин.
/ цикл замкнутая цепь
Расстояние между вершинами – длина кратчайшей цепи между данными вершинами.
Связные вершины - две вершины, для которых существует хотя бы одна соединяющая их цепь.
Связный граф – граф в котром каждые две вершины связаны
Компоненты связности – классы эквивалентности из которых состоит граф
Степень связности графа – число компонент связности графа
Эйлеров цикл – цикл содержащий все ребра графа
Эйлеров граф – граф в котором есть эйлеров цикл
полуэйлеров граф – граф в котором есть разомкнутая эйлерова цепь
Гамильтонова линия – цикл содержащий все вершины графа равно по одному разу
23. Гамильтонов граф – граф содержащий гамильтонову линию
полугамильтонов граф – граф содержащий разомкнутую гамильтонову линию
24. Двудольный граф – граф с множеством вершин v , в котором каждое ребро соединяет вершину из множества v1, с какой-либо вершиной из множества v2
25. Полный двудольный граф – двудольный граф , в котором каждая вершина из множества v1 соединена с каждой вершиной из множества v2.
26. Диаметр – число ребер наибольшей из минимальных цепей в графе
радиус графа – наименьший из эксцентриситетов
эксцентриситет вершины – наибольшее расстояние междк заданной вершиноц и другими вершинами графа
27. Плоский - граф, изображённый на плоскости так что его ребра пересекаются только в вершинах
планарный граф – граф, изоморфный плоскому графу

28. Грань – часть плоскости, огрониченная со всех сторон ребрами и не содержащая внутри себя ни вершин ни других ребер

29. Двойственный граф - граф G*, построенный следующим образом: 1) каждой грани G ставится в соответствие вершина G*; 2) висячая вершина в G порождает петлю в G*; 3) если вершина G* отделена от другой вершины G* ребром G, то эти две вершины соединяются ребром в G*.

30. Разделяющее множество – множество ребер графа после удаления которых получается несвязный граф

Разрез – разделяющее множество у которого нет собственного разделяющего подмножества.

31. Лес – несвязный граф, не содержащий циклов

Дерево – связный граф, не содержащий циклов

32. Остов графа – связный частичный граф G не содержащий циклов

33. Цикломатическое число – число, показывающее, какое наименьшее количество ребер надо удалить из графа, чтобы получить его остов.
34. Ориентированный граф – граф, содержащий только дуги
смешанный граф – граф, содержащий и дуги и неориентированные ребра

35. Основание орграфа – граф, полученный из орграфа заменой всех дуг на ребра

36. Степень входа – число входящих в вершину дуг
выхода вершины в орграфе – число исходящих из вершины дуг
37. Достижимость вершины в орграфе – если существует маршрут из вершины v1 в вершину v2, то вершина v1 называется Достижимость вершины в орграфе
38. Сильносвязный - орграф, в котором существует простая ориентированная цепь , соединяющая любые две его вершины
слабосвязный - орграф, основанием которого является связный граф
несвязный орграф – орграф, основанием которого является граф с числом компонент, превышающем единицу
39. Полный орграф – орграф, основанием которого является полный граф
40. Транспортная сеть – орграф , в котором ровно одна вершина с нулевой степенью входа и ровно одна вершина с нулевой степенью выхода, и где каждой дуге поставлено в соответствие число.
41. Поток в сети - функция f(vi,vj), которая: 1)0fvi,vjc(vi,vj) (vi,vj)
2) f vi , v j    f v j , vi 
3)fvi,ufu,vj fu,v0 uV,us,t

42. Разрез – разбиение множества всех вершин v на два подмножества а и в так, что VA B,A B,sA,tB

минимальный разрез сети - разрез, суммарная пропускная способность дуг которого является наименьшей