ребрам графа можно сопоставить
тесты2
Структура данных представляет собой
набор правил и ограничений, определяющих связи между отдельными элементами и группами данных
набор правил и ограничений, определяющих связи между отдельными элементами данных
набор правил и ограничений, определяющих связи между отдельными группами данных
некоторую иерархию данных
Линейный список, в котором доступен только последний элемент, называется
Линейный последовательный список, в котором включение исключение элементов возможно с обоих концов, называется
открыта с обеих сторон ;
открыта с одной стороны на вставку и удаление;
доступен любой элемент.
открыт с обеих сторон на вставку и удаление;
доступен любой элемент;
открыт с одной стороны на вставку и удаление.
12. Как создать пустой элемент с указателем p? a) p=getnode; b) info(p); c) freenode(p); d) ptr(p)=lst.
13Сколько указателей используется в односвязных списках? a) 1 b) 2; c) сколько угодно.
Элемент дерева, который не ссылается на другие, называется
19.Элемент дерева, на который не ссылаются другие, называется
20. Элемент дерева, который имеет предка и потомков, называется
Высотой дерева называется
максимальное количество узлов
максимальное количество связей
максимальное количество листьев
максимальная длина пути от корня до листа
22. Степенью дерева называется
максимальная степень всех узлов
максимальное количество уровней его узлов
максимальное количество узлов
максимальное количество связей
максимальное количество листьев
Как определяется длина пути дерева
как сумма длин путей всех его узлов
как количество ребер от узла до вершины
как количество ребер от листа до вершины
как максимальное количество ребер
как максимальное количество листьев
как длина самого длинного пути от ближнего узла до какого-либо листа
Дерево называется бинарным, если
количество узлов может быть либо пустым, либо состоять из корня с двумя другими бинарными поддеревьями
каждый узел имеет не менее двух предков
от корня до листа не более двух уровней
от корня до листа не менее двух уровней
множество узлов, которое
Бинарное дерево можно представить
с помощью указателей
с помощью массивов
с помощью индексов
правильного ответа нет
Какой метод поиска представлен в следующем фрагменте REPEAT I:=I+1 UNTIL (A[I]=X) OR (I=N);
Какой метод поиска представлен в следующем фрагменте
REPEAT K:=(I+J)DIV 2; IF X>A[K] THEN I=K+1 ELSE J:=K-1;
Реализация поиска в линейном списке выглядит следующим образом
WHILE (P<>NIL) AND (P^.KEY<>X) DO P:=P^.NEXT
WHILE (P<>NIL) DO P:=P^.NEXT
WHILE AND (P^.KEY<>X) DO P:=P^.NEXT
WHILE (P<>NIL) AND (P^.KEY<>X) P:=P^.NEXT
WHILE (P<>NIL P^.KEY<>X) DO P:=P^.NEXT
Как называются предки узла, имеющие уровень на единицу меньше уровня самого узла
В графах общая идея поиска в глубину состоит в следующем:
Поиск начинаем с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0, и повторяем просмотр от u. Предположим, что находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, u—v, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v, не существует, то возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=v0, то поиск закончен);
Поиск начинаем с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0, и повторяем просмотр от u. Предположим, что находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, u-v, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v, не существует, то возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=u, то поиск закончен);
Поиск начинаем с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину u, смежную с v0, и повторяем просмотр от u. Предположим, что находимся в некоторой вершине v. Если существует ещё не просмотренная вершина u, то рассматриваем её, затем продолжаем поиск с нее. Если не просмотренной вершины, смежной с v, не существует, то возвращаемся в вершину, из которой попали в v, и продолжаем поиск (если v=v0, то поиск закончен).
Стандартным способом устранения рекурсии при поиске в глубину является использование:
Ребрам графа можно сопоставить
Граф — упорядоченная пара (V, E), где V — непустое множество вершин, E — множество (или мультмножество в случае мультгирафов) пар вершин ( ребер ).
Многие практически и олимпиадные задачи сводятся к графам. Например, графом можно описать сеть дорог, схему метро, электрическую цепь и т.д. Введем основные понятия для графов.
Хранение графов в памяти
Во-первых, будем считать, что все вершины пронумерованы от 1 до N. Если это не так, то мы можем перенумеровать имеющиеся вершины.
Для небольших графов удобно использовать матрицу смежности A = < a_ij >, где a_ij = 1, если есть ребро (i, j), иначе 0. Заметим, что матрица смежности неориентированного графа симметрична относительно главной диагонали. Матрица смежности требует O(N^2) памяти, поэтому ее применение ограничивается графами с числом вершин порядка 1000.
Для графов с большим числом вершин, но относительно малым числом ребер (такие графы называют разряженными ) необходимо применять связные списки с несколькими головами (см. «Списки, стеки, очереди»). Также можно применять структуры данных реализованные в стандартных библиотеках: stl::vector в C++ (удобно и быстро) и ArrayList в Java (не очень удобно и достаточно медленно).
Стоит отметить, что иногда граф вообще не нужно хранить в памяти. Обычно это возможно, если граф полный, и вес каждого ребра однозначно восстанавливается по номерам вершин (например, даны точки на плоскости).
Алгоритмы
Сначала рассмотрим алгоритмы обхода графа. Они являются основой для многих алгоритмов (поиск путей, топологическая сортировка, поиск циклов, поиск максимального потока и др.).
Поиск в глубину
Поиск в глубину (Depth-first search, DFS) заключается в следующем: фиксируем текущую вершину, помечаем ее как посещенную, и пока есть смежные с ней не посещенные вершины, рекурсивно их обходим. Для определения того, что вершина посещена, обычно используется массив флагов.
Реализация на Java:
Можно реализовать и нерекурсивный вариант поиска в глубину, используя стек.
Поиск в ширину (Breadth-first search, BFS)
Поиск в ширину фактически тоже самое что нерекурсивный поиск в глубину, только в место стека используется очередь. Его идея заключается в том, что на каждой итерации все не рассмотренные вершины, смежные с текущей добавляются в очередь, и затем текущей становится вершина, извлеченная из очереди. Основное свойство поиска в ширину в том, что расстояние (количество ребер в пути) от любой текущей вершины до исходной (из которой запущен BFS) минимально.
Рассмотрим простейшую реализацию на Java:
Поиск компонент связности
Теперь рассмотрим простейшее применение рассмотренных алгоритмов. Попробуем найти связные компоненты неориентированного графа. Поставим следующую задачу: найти количество компонент связности и для каждой вершины определить, к какой компоненте она принадлежит.
Заметим, что если запустить обход из любой вершины какой-нибудь компоненты, то мы обойдем все вершины данной компоненты. Таким образом получаем следующий алгоритм: перебираем вершины, если текущая не помечена, увеличиваем счетчик компонент, и запускаем из текущей вершины поиск в глубину или ширину. Каждой вершине при обходе сопоставляем номер текущей компоненты.
math4school.ru
Графы, отображения
Немного теории
Изображая элементы некоторого множества точками и соединяя некоторые пары точек отрезками, мы получаем наглядное представление для очень популярного объекта дискретной математики. Он называется графом; точки (элементы множества) называются вершинами, отрезки (или дуги) – рёбрами графа. Некоторые вершины графа могут быть не соединены рёбрами. Точки пересечения рёбер графа на его изображении не всегда считаются его вершинами, поэтому вершины графа часто выделяют кружочками.
Вершина называется чётной (нечётной), если она принадлежит чётному (нечётному) числу рёбер. Граф называется чётным, если все его вершины чётные.
Теорема. Количество нечётных вершин в любом графе – чётное число.
Последовательность различных рёбер графа, каждое последующее из которых начинается в конце предыдущего, называется путём. Путь, в котором никакое ребро не встречается дважды, называется простым.
Граф, из любой вершины которого можно пройти в любую другую путём, состоящим из ребер, называется связным. Замкнутый путь по ребрам графа называется циклом. Цикл, который содержит все рёбра графа, называется обходом графа. Обход, при котором каждое ребро графа проходится только один раз, называется правильным.
Теорема. Для произвольного связного чётного графа существует правильный обход, который можно начать в любой вершине и который обязательно заканчивается в ней же.
Теорема. Если связный граф имеет ровно две нечётные вершины, то для него существует правильный обход, причём этот обход в одной нечётной вершине начинается, а в другой – заканчивается.
Теорема. Если в графе больше двух нечётных вершин, то для него невозможен правильный обход.
Связный граф без циклов называется деревом.
Теорема. Граф является деревом тогда и только тогда, когда любые две его вершины соединены ровно одним простым путём.
Теорема. Дерево имеет вершин на одну больше, чем рёбер.
Если все циклы графа имеют чётную длину, то его вершины можно раскрасить в два цвета так, что вершины одного цвета не соединены ни одним ребром; такой граф называется двудольным.
Если на ребрах графа расставить стрелки, то получится ориентированный граф (орграф). Любое отображение f конечного множества А в себя задаёт орграф, из каждой вершины а (элемент множества А) которого выходит одна стрелка – в вершину f(а). (При этом возможны и петли – стрелки, идущие из а в а; они соответствуют неподвижным точкам отображения f.) Если f взаимно однозначное отображение множества А в себя, то орграф распадается на циклы и петли.
Граф, который можно нарисовать так, чтобы его рёбра не пересекались (нигде, кроме вершин), называется плоским (а такое изображение правильным).
Теорема Эйлера. Для правильно изображённого связного плоского графа выполняется равенство:
где В – количество вершин графа, где Г – количество частей (граней), на которые плоский граф разбивает плоскость, где Р – количество рёбер графа.
Теорема Эйлера справедлива так же для произвольного выпуклого пространственного многогранника.
Один из примеров сложного графа – схема телефонной сети.
При решении задач рассматриваются также графы, рёбра или вершины которых раскрашены в несколько цветов, или помечены числами.
Задачи с решениями
1. Существует ли замкнутая ломаная, которая пересекает каждое своё звено ровно один раз и состоит из:
а) Для любого чётного n > 6 существует замкнутая ломаная из n звеньев, пересекающая каждое своё звено ровно один раз. Пример для n = 6 показан на рисунке 1. Для n > 8 на рисунке 2 показана конструкция части ломаной (правило построения остальной части ясно).
б) Предположим, что удалось построить такую ломаную. Рассмотрим какую-нибудь точку её самопересечения. В ней пересекаются два звена, причём больше ни с какими другими звеньями они не пересекаются. Поэтому все звенья ломаной можно разбить на пары, соответствующие её точкам самопересечения. Значит, звеньев – чётное число и их не может быть семь.
Это рассуждение показывает, что вообще не существует ломаной с нечётным числом звеньев, пересекающей каждое своё звено ровно один раз.
Ответ: не существует.
2. В обществе, состоящем из 2013 человек, среди любых четырех человек можно выбрать, по крайней мере, одного, знакомого с остальными тремя. Каково минимально возможное количество людей, которые знакомы со всеми?
Если незнакомых людей нет, то количество людей, которые знакомы со всеми, равно 2013. Пусть А и В не знакомы друг с другом. Тогда все остальные люди между собой знакомы (если С не знаком с D, то в группе A, B, С, D никто не знаком с остальными тремя). Если А и В знакомы со всеми остальными, то 2011 человек знакомы со всеми. Если же А не знаком также и с С, где С и В различны, то и A, и В, и С знакомы со всеми остальными 2010 людьми (так как в любой группе А, B, С, D только D может быть знакомым с остальными тремя), которые к тому же знакомы между собой. Таким образом, минимальное количество людей, знакомых со всеми, равно 2010.
3. В трёх вершинах правильного пятиугольника расположили по фишке. Разрешается передвигать их по диагонали в любую свободную вершину. Можно ли таким образом добиться того, чтобы одна из фишек вернулась на свое место, а две другие поменялись местами?
Последовательно пронумеруем вершины пятиконечной звезды (полученной в результате возможных перемещений фишек) числами 1, 2, 3, 4, 5. Видим, что из вершины 1 можно за один ход попасть в вершину 3 или в вершину 4; из вершины 2 – или в вершину 4, или в вершину 5; из вершины 3 – или в вершину 5, или в вершину 1; из вершины 4 – или в вершину 1, или в вершину 2; из вершины 5 – или в вершину 2, или в вершину 3. Эти перемещения становятся более «естественными», если такую пятиконечную звезду «развернуть» в пятиугольник с вершинами пронумерованными в таком порядке: 1, 3, 5, 2, 4.
Тогда перемещениям по сторонам звезды соответствуют перемещения фишек по сторонам пятиугольника из некоторой вершины в одну из соседних (если она не занята). Очевидно, что с помощью таких перемещений по сторонам пятиугольника нельзя изменить порядок размещения фишек, а, значит, нельзя добиться того, чтобы одна из фишек на звезде вернулась на своё место, а две другие поменялись местами.
4. Все грани выпуклого многогранника являются треугольниками. Докажите, что каждое ребро этого многогранника можно покрасить в красный или синий цвет так, чтобы в итоге из любой его вершины в любую другую можно было попасть, двигаясь только по красным ребрам, а также только по синим.
5. В некотором государстве система авиалиний устроена таким образом, что каждый город соединен авиалиниями не более чем с тремя другими, и из каждого города можно попасть в любой другой, сделав не более одной пересадки.
Какое наибольшее количество городов может быть в этом государстве?
Из любого города А можно добраться не более чем до трёх городов, а из каждого из них не более чем до двух (не считая А). Таким образом, всего городов не более, чем
Пример на следующем рисунке показывает, что нужная система авиалиний с десятью городами существует.
Замечание. То, что речь идёт об одном примере, а не о двух – не оговорка. Приведённые выше два графа изоморфны и могут, в некотором смысле, считаться одним и тем же графом. (Два изоморфных графа встречаются и в решении задачи 3.) Этот граф в теории графов часто используется в качестве примера и даже имеет специальное название «граф Петерсена».
6. Клетчатая плоскость раскрашена десятью красками так, что соседние (то есть имеющие общую сторону) клетки покрашены в разные цвета, причём все десять красок использованы. Каково минимально возможное число пар соседних красок? (Две краски называются соседними, если ими покрашены какие-то две соседние клетки.)
Следующий рисунок даёт зрительное представление предложенного способа раскраски плоскости.
1) для любых различных элементов a и b из S выполнено ровно одно из отношений а → b или b → а;
2) для любых трех различных элементов a, b, c из S выполнение отношений а → b и b → c влечет за собой выполнение отношения с → а.
Каково наибольшее число элементов, которое может содержать множество S?
Предположим, что в множестве S найдутся три элемента a, b, c такие, что а → b и а → с. Если b → c, то из а → b и b → с следует с → а, что противоречит условию а → с. Если же с → b, то из а → с и с → b следует b → а, что противоречит условию а → b.
Аналогично доказывается, что в S нет элементов а, d, е таких, что d → а и e → а.
Если в множестве S имеется 4 или более элементов (один из которых обозначим через а), то из первого условия задачи следует, что в S найдутся или такие элементы b и с, что а → b и а → с, или же такие элементы d и е, что d → а и е → a. В обоих случаях получаем противоречие. Поэтому в множестве S не более трех элементов.
Пример множества S с тремя элементами а, b, с, удовлетворяющего обоим условиям задачи, может быть таким: а → b, b → с, с → а.
8. Муха села на вершину модели правильного додекаэдра (рисунок 1) и решила обойти его, двигаясь по ребрам додекаэдра; при этом ей удалось посетить все вершины, не побывав ни в одной из них дважды и вернувшись в конце путешествия в исходную вершину. После этого она попробовала обойти тем же способом все вершины ромбического додекаэдра, ограниченного 12 ромбами (рисунок 2). Удалось ли ей это?
Многогранник образует пространственную сеть, сторонами которой являются ребра, узлами – вершины, а ячейками грани многогранника. Дорога мухи должна образовать замкнутую ломаную линию, без кратных точек, принадлежащую указанной выше сети. Возможность выделения такой дороги сохранится, если мы деформируем сеть так, чтобы уместить ее на плоскости.
На рисунке 3 мы видим растянутую на плоскости сеть ребер правильного додекаэдра. Зеленой линией обозначен путь мухи, отвечающий условию задачи.
Теперь подобным же образом растянем на плоскости сеть ромбического додекаэдра (рисунок 4). Узлы сети можно разделить на два класса: на такие, в которых сходятся три ребра, и на такие, в которых сходятся четыре ребра (на рисунке узлы подписаны соответствующим образом).
Каждый узел первого класса соединен отрезком только с узлами второго класса, и наоборот. Поэтому муха во время своего путешествия должна была проходить поочередно через узлы первого класса и узлы второго класса. Так как узлов первого класса восемь, а узлов второго класса шесть, то муха не может посетить всех вершин ромбического додекаэдра, передвигаясь по ребрам так, чтобы не пройти через одну вершину дважды и вернуться к исходной точке.
9. В ориентированном графе 101 вершина. У каждой вершины число входящих и число выходящих ребер равно 40. Доказать, что из любой вершины можно попасть в любую, проходя не более чем по трём ребрам.
Пусть a и b – две вершины данного графа, A – множество из 40 вершин, в которые ведут рёбра из a, B – множество из 40 вершин, из которых идут рёбра в b, C – множество из оставшихся вершин.
Предположим, что из a нельзя пройти в b по трём рёбрам. Тогда все рёбра, выходящие из A, идут в A или в C. Этих рёбер по условию всего 40·40 = 1600. Но рёбер внутри A не больше чем (40·39)/2 = 780, а рёбер, которые выходят из А в С не больше чем 40·19 = 760, что в сумме даёт 1540 Решение
Будем решать задачу индукцией по n – числу юношей. Для n = 1 утверждение вытекает из того, что для одного юноши обязательно найдется знакомая девушка. Пусть утверждение доказано для всех чисел, меньших n. Докажем его для числа n. Рассмотрим два случая.
1) Найдется такая группа А из k n – 1 оставшихся юношей знакома не менее чем с k + 1 девушками (одна из которых, возможно, уже танцует). Значит, по предположению индукции, каждый из оставшихся юношей также сможет танцевать со знакомой ему девушкой.
Задачи без решений
1. В некотором обществе любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Доказать, что в этом обществе все имеют одинаковое число знакомых.
2. В стране любые два города соединены дорогой с односторонним движением. Доказать, что существует город, из которого можно проехать в любой другой не более чем по двум дорогам.
3. В розыгрыше первенства страны по футболу участвуют 20 команд. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трёх команд нашлись две, уже сыгравшие между собой?
4. В некотором поселке 1000 жителей. Ежедневно каждый из них делится узнанными вчера новостями со всеми своими знакомыми. Известно, что любая новость становится известной всем жителям поселка. Докажите, что можно выбрать 90 жителей так, что если одновременно всем им сообщить какую-то новость, то через 10 дней она станет известной всем жителям поселка.
5. В некоторой стране из каждого города в любой другой можно проехать, минуя остальные города. Известна стоимость каждого такого проезда. Составлены два маршрута поездки по городам страны. В каждый из этих маршрутов каждый город входит ровно по одному разу. При составлении маршрута руководствовались следующим принципом: начальный пункт маршрута выбирается произвольно, а на каждом следующем шаге среди городов, через которые маршрут ещё не проходил, выбирается тот, поездка в который из предыдущего города имеет наименьшую стоимость (если таких городов несколько, то выбирается любой из них); и так до тех пор, пока не будут пройдены все города. При составлении второго маршрута начальный город тоже выбирается произвольно, а на каждом следующем шаге среди городов, через которые маршрут ещё не проходил, выбирается тот, поездка в который из предыдущего города имеет наибольшую стоимость. Докажите, что общая стоимость проезда по первому маршруту не больше общей стоимости проезда по второму маршруту.
Теория графов. Основные понятия и виды графов
Теория графов
В переводе с греческого граф — «пишу», «описываю». В современном мире граф описывает отношения. И наоборот: любое отношение можно описать в виде графа.
Теория графов — обширный раздел дискретной математики, в котором системно изучают свойства графов.
Теория графов широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике и в других областях.
Для чего строят графы: чтобы отобразить отношения на множествах. По сути, графы помогают визуально представить всяческие сложные взаимодействия: аэропорты и рейсы между ними, разные отделы в компании, молекулы в веществе.
Давайте на примере.
На множестве A зададим отношение знакомства между людьми из этого множества. Строим граф из точек и связок. Связки будут связывать пары людей, знакомых между собой.
Число знакомых у одних людей может отличаться от числа знакомых у других людей, некоторые могут вовсе не быть знакомы (такие элементы будут точками, не соединёнными ни с какой другой). Так получился граф:
В данном случае точки — это вершины графа, а связки — рёбра графа.
Теория графов не учитывает конкретную природу множеств A и B. Существует большое количество разных задач, при решении которых можно временно забыть о содержании множеств и их элементов. Эта специфика не отражается на ходе решения задачи.
Например, вопрос в задаче стоит так: можно ли из точки A добраться до точки E, если двигаться только по соединяющим точки линиям. Когда задача решена, мы получаем решение, верное для любого содержания, которое можно смоделировать в виде графа.
Не удивительно, что теория графов — один из самых востребованных инструментов при создании искусственного интеллекта: ведь искусственный интеллект может обсудить с человеком вопросы отношений, географии или музыки, решения различных задач.
Графом называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.
Пусть V — (непустое) множество вершин, элементы v ∈ V — вершины. Граф G = G(V) с множеством вершин V есть некоторое семейство пар вида: e = (a, b), где a, b ∈ V, указывающих, какие вершины остаются соединёнными. Каждая пара e = (a, b) — ребро графа. Множество U — множество ребер e графа. Вершины a и b — концевые точки ребра e.
Широкое применение теории графов в компьютерных науках и информационных технологиях можно объяснить понятием графа как структуры данных. В компьютерных науках и информационных технологиях граф можно описать, как нелинейную структуру данных.
Линейные структуры данных особенны тем, что связывают элементы отношениями по типу «простого соседства». Линейными структурами данных можно назвать массивы, таблицы, списки, очереди, стеки, строки. В нелинейных структурах данных элементы располагаются на различных уровнях иерархии и подразделяются на три вида: исходные, порожденные и подобные.
Основные понятия теории графов
Граф — это геометрическая фигура, которая состоит из точек и линий, которые их соединяют. Точки называют вершинами графа, а линии — ребрами.
Лемма о рукопожатиях
В любом графе сумма степеней всех вершин равна удвоенному числу ребер.
Доказательство леммы о рукопожатиях
Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней вершин мы учтем это ребро дважды.
Если же ребро является петлей — при подсчете суммы степеней вершин мы также учтем его дважды (по определению степени вершины).
Из леммы о рукопожатиях следует: в любом графе число вершин нечетной степени — четно.
Пример 1. В классе 30 человек. Может ли быть так, что у 9 из них есть 3 друга в этом классе, у 11 — 4 друга, а у 10 — 5 друзей? Учесть, что дружбы взаимные.
Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — со степенью 4, 10 — со степенью 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях.
Пример 2. Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Доказать, что среди них найдутся четверо ребят с одинаковым числом знакомых.
Сначала предположим противоположное. Тогда для каждого числа от 68 до 101 есть не более трех человек с таким числом знакомых. С другой стороны, у нас есть ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 34 * 3.
Это значит, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.
Путь и цепь в графе
Путем или цепью в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Циклом называют путь, в котором первая и последняя вершины совпадают.
Путь или цикл называют простым, если ребра в нем не повторяются.
Если в графе любые две вершины соединены путем, то такой граф называется связным.
Можно рассмотреть такое подмножество вершин графа, что каждые две вершины этого подмножества соединены путем, а никакая другая вершина не соединена ни с какой вершиной этого подмножества.
Каждое такое подмножество, вместе со всеми ребрами исходного графа, соединяющими вершины этого подмножества, называется компонентой связности.
Один и тот же граф можно нарисовать разными способами. Вот, например, два изображения одного и того же графа, которые различаются кривизной:
Два графа называются изоморфными, если у них поровну вершин. При этом вершины каждого графа можно занумеровать числами так, чтобы вершины первого графа были соединены ребром тогда и только тогда, когда соединены ребром соответствующие занумерованные теми же числами вершины второго графа.
Граф H, множество вершин V’ которого является подмножеством вершин V данного графа G и множество рёбер которого является подмножеством рёбер графа G соединяющими вершины из V’ называется подграфом графа G.
Визуализация графовых моделей
Визуализация — это процесс преобразования больших и сложных видов абстрактной информации в интуитивно-понятную визуальную форму. Другими словами, когда мы рисуем то, что нам непонятно — и сразу все встает на свои места.
Графы — и есть помощники в этом деле. Они помогают представить любую информацию, которую можно промоделировать в виде объектов и связей между ними.
Граф можно нарисовать на плоскости или в трехмерном пространстве. Его можно изобразить целиком, частично или иерархически.
Изобразительное соглашение — одно из основных правил, которому должно удовлетворять изображение графа, чтобы быть допустимым. Например, при изображении блок-схемы программы можно использовать соглашение о том, что все вершины должны изображаться прямоугольниками, а дуги — ломаными линиями с вертикальными и горизонтальными звеньями. При этом, конкретный вид соглашения может быть достаточно сложен и включать много деталей.
Виды изобразительных соглашений:
Виды графов
Виды графов можно определять по тому, как их построили или по свойствам вершин или ребер.
Ориентированные и неориентированные графы
Графы, в которых все ребра являются звеньями, то есть порядок двух концов ребра графа не существенен, называются неориентированными.
Графы, в которых все ребра являются дугами, то есть порядок двух концов ребра графа существенен, называются ориентированными графами или орграфами.
Неориентированный граф можно представить в виде ориентированного графа, если каждое его звено заменить на две дуги с противоположным направлением.
Графы с петлями, смешанные графы, пустые графы, мультиграфы, обыкновенные графы, полные графы
Если граф содержит петли — это обстоятельство важно озвучивать и добавлять к основной характеристике графа уточнение «с петлями». Если граф не содержит петель, то добавляют «без петель».
Смешанным называют граф, в котором есть ребра хотя бы двух из упомянутых трех разновидностей (звенья, дуги, петли).
Пустой граф — это тот, что состоит только из голых вершин.
Мультиграфом — такой граф, в котором пары вершин соединены более, чем одним ребром. То есть есть кратные рёбра, но нет петель.
Граф без дуг, то есть неориентированный, без петель и кратных ребер называется обыкновенным.
Граф называют полным, если он содержит все возможные для этого типа рёбра при неизменном множестве вершин. Так, в полном обыкновенном графе каждая пара различных вершин соединена ровно одним звеном.
Двудольный граф
Граф называется двудольным, если множество его вершин можно разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества.
Например, полный двудольный граф состоит из двух множеств вершин и из всевозможных звеньев, которые соединяют вершины одного множества с вершинами другого множества.
Эйлеров граф
Эйлеров граф отличен тем, что в нем можно обойти все вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное число рёбер.
Пример. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом?
Регулярный граф
Регулярным графом называется связный граф, все вершины которого имеют одинаковую степень k.
Число вершин регулярного графа k-й степени не может быть меньше k + 1. У регулярного графа нечётной степени может быть лишь чётное число вершин.
Пример. Построить регулярный граф, в котором самый короткий цикл имеет длину 4.
Чтобы длина цикла соответствовала заданному условию, нужно чтобы число вершин графа было кратно четырем. Если число вершин равно четырём — получится регулярный граф, в котором самый короткий цикл имеет длину 3.
Увеличим число вершин до восьми (следующее кратное четырем число). Соединим вершины ребрами так, чтобы степени вершин были равны трём. Получаем следующий граф, удовлетворяющий условиям задачи:
Гамильтонов граф
Гамильтоновым графом называется граф, содержащий гамильтонов цикл.
Гамильтоновым циклом называется простой цикл, который проходит через все вершины рассматриваемого графа.
Говоря проще, гамильтонов граф — это такой граф, в котором можно обойти все вершины, и каждая вершина при обходе повторяется лишь один раз.
Взвешенный граф
Взвешенным графом называется граф, вершинам и/или ребрам которого присвоены «весы» — обычно некоторые числа. Пример взвешенного графа — транспортная сеть, в которой ребрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг.
Графы-деревья
Деревом называется связный граф без циклов. Любые две вершины дерева соединены лишь одним маршрутом.
Приведенное соотношение выражает критическое значение числа рёбер дерева, так как, если мы присоединим к дереву ещё одно ребро — будет создан цикл. А если уберем одно ребро, то граф-дерево разделится на две компоненты. Граф, состоящий из компонент дерева, называется лесом.
Определение дерева
Деревом называется связный граф, который не содержит циклов.
Таким образом, в дереве невозможно вернуться в исходную вершину, перемещаясь по ребрам и не проходя по одному ребру два или более раз.
Циклом называется замкнутый путь, который не проходит дважды через одну и ту же вершину.
Простым путем называется путь, в котором никакое ребро не встречается дважды.
Легко проверить, что дерево — это граф, в котором любые две вершины соединены ровно одним простым путем. Если выкинуть любое ребро из дерева, то граф станет несвязным. Поэтому:
Дерево — минимальный по числу рёбер связный граф.
Висячей вершиной называется вершина, из которой выходит ровно одно ребро.
Определения дерева:
Очень часто в дереве выделяется одна вершина, которая называется корнем дерева. Дерево с выделенным корнем называют корневым или подвешенным деревом. Пример: генеалогическое дерево.
Когда изображают деревья, то часто применяют дополнительные соглашения, эстетические критерии и ограничения.
Например, при соглашении включения (рис. 1) вершины корневого дерева изображают прямоугольниками, а соглашение — опрокидывания (рис. 2) подобно классическому соглашению нисходящего плоского изображения корневого дерева. Вот так могут выглядеть разные изображения одного дерева:
Теоремы дерева и их доказательства
В дереве с более чем одной вершиной есть висячая вершина.
Доказательство первой теоремы:
Пойдем из какой-нибудь вершины по ребрам. Так как в дереве нет циклов, то мы не вернемся в вершину, в которой уже побывали. Если у каждой вершины степень больше 1, то найдется ребро, по которому можно уйти из неё после того, как мы пришли в нее.
Но поскольку количество вершин в дереве конечно, когда-нибудь мы остановимся в некоторой вершине. Противоречие. Значит, когда-нибудь мы дойдём в висячую вершину. Если же начать идти из неё, то мы найдём вторую висячую вершину.
В дереве число вершин на 1 больше числа ребер.
Доказательство второй теоремы:
Докажем по индукции по количеству вершин в дереве n. Если в дерево одна вершина, то факт верен. Предположим, что для всех n
