1. Определение графа
Как было сказано во введении, первая работа по теории графов принадлежит Л.Эйлеру, и опубликована она была в 1736 г., однако термин “граф” впервые появился в книге венгерского математика Д. Кенига в 1936 г.
Дадим определение графа.
Пусть V- непустое множество,V{2}- множество всех его двухэлементных подмножеств. Пара (V,E), гдеЕV{2}называетсяграфом(неориентированным графом).
Граф называется конечным, если множествоVконечно. В дальнейшем под термином “граф” будем понимать конечные графы.
Элементы множества Vназываютсявершинамиграфа, а элементы множестваЕназываютрёбрами графа.
Число вершин графа G=(V,E) называется егопорядком.
Исходя из определения графа, каждому ребру соответствует двухэлементное подмножество вершин. Если подмножество {v1,v2} соответствует ребруе, то говорят, что реброеинцидентновершинамv1иv2, а вершиныv1иv2смежны. Также говорят, что реброесоединяет вершиныv1иv2. Вершиныv1иv2называются концевыми вершинами ребрае.
Граф можно представить графически: каждая вершина представляется точкой или окружностью, а каждое ребро представляется отрезком, соединяющим его концевые вершины.
Граф G=(V,E),V={v1,v2,v3,v4},E={{v1,v2}, {v1,v4}, {v2,v3}, {v2,v4}, {v3,v4}} представлен графически на рис.1.1.
Обобщим понятие графа.
Мультиграф– это пара (V,E), гдеV- непустое множество, аE- семейство подмножеств множестваV{2}.
Употребление термина “семейство” вместо “подмножество” означает, что элементы множества V{2}могут вEповторяться, то есть допускаютсякратные рёбра.
Пример мультиграфа показан на рис. 1.2.
Дальнейшее обобщение состоит в том, что кроме кратных рёбер допускаются еще петли, то есть рёбра, соединяющие вершину саму с собой.
Такой граф называется псевдографом. Его пример приведен на рис. 1.3.
Псевдограф – это пара (V,E), гдеV- непустое множество (вершин), аE- некоторое семейство неупорядоченных пар вершин (рёбер), не обязательно различных.
Различают также ориентированные и смешанные графы.
Пусть V(2) - множество упорядоченных пар элементов множестваV. Тогдаориентированный граф(илиорграф) - это пара (V,А), гдеV- множество вершин,АV(2)- множество ориентированных рёбер, которые называютсядугами.
Если пара (v1,v2) - дуга, то вершиныv1иv2называются её началом и концом соответственно.
На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу.
Орграф G=(V,E),V={v1,v2,v3,v4},E={(v1,v2), (v1,v4), (v2,v3), (v2,v4), (v3,v4)} представлен графически на рис.1.4.
Ориентированный мультиграфиориентированный псевдографопределяются аналогично.
Смешанные графыимеют как дуги, так и неориентированные рёбра.
Пример смешанного графа представлен на рис. 1.5.
Ради сокращения речи термин “граф” употребляется вместо терминов “мультиграф”, ”орграф” и др., но подобные случаи либо специально оговариваются, либо ясны из контекста.
Часто каждой дуге графа ставят в соответствие одно или несколько чисел. Такой граф называется взвешенным(илисетью). Пример взвешенного графа представлен на рис. 1.6.
