Вершины в графе могут отличаться друг от друга тем, скольким ребрам они принадлежат. Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Степенью выхода вершины А ориентированного графа называют число выходящих из А ребер. Степенью входа вершины А ориентированного графа называется число входящих в А ребер. Существует набор функций, определяющий степени вершин. Функция vdegree() работает с неориентированными ребрами, indegree() - с ориентированными ребрами, входящими в данную вершину, а outdegree() - с ориентированными ребрами, выходящими из данной вершины.

> with(networks):

> G:=void(7): connect({1, 2}, {3, 4, 5}, G): connect({1}, {6, 7}, G): draw(G); vdegree(1, G); indegree(1, G); outdegree(1, G);

Обозначение степени вершины A - p(A). Вершина называется нечетной , если ее степень - число нечетное. Вершина называется четной, если ее степень - число четное. Число ребер графа мы считали с помощью функции nops(), но можно сосчитать число ребер в каждой вершине, отдельно и сложить все эти числа. При этом каждое ребро будет сосчитано дважды - соответственно двум вершинам, которые оно соединяет, поэтому общее число ребер графа N будет равно половине этой суммы:

N=1/2( p() + p () +...+ p()

Очевидно, что для любого графа сумма степеней всех его вершин является четным числом, поскольку она равна удвоенному числу ребер этого графа. Проверим это. Функция degreeseq() выводит список всех степеней вершин графа в порядке возрастания. А с помощью функции add() можно подсчитать сумму всех степеней вершин графа:

> degreeseq(G);

> add(i,i=degreeseq(G));

Мы можем найти количество ребер данного графа, разделив полученную сумму пополам, т.е. количество ребер равно 8. Проверим результат с помощью следующей функции:

> nops(edges(G));

Рассмотрим задачу:

Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?

Предположим, что можно. Создадим граф данной ситуации. Возьмем за вершины графа данные отрезки. Ребрами будем соединять те вершины (отрезки), которые пересекаются. Получили граф с 9 вершинами, и степень каждой из вершин равна 3. Подсчитаем сколько ребер в получившемся графе:

9*3/2=13,5

Получили противоречие, т.к. число ребер графа - число целое. Вывод - нельзя. Интересные факты: Сумма степеней входа всех вершин равна числу ребер графа и равна сумме степеней выхода всех его вершин. Во всяком графе с n вершинами, где n>=2, всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.

4. Циклы и пути в графе

Рассмотрим следующий граф:

> with(networks):

> H:=void(5): connect({4}, {1, 2, 3, 5}, H): addedge([{1, 2}, {1, 3}], H): draw(Linear([1], [3, 2], [4], [5]), H);

Как пройти по ребрам на рис.1 из вершины 1 в вершину 5?

Вот, к примеру, три последовательности ребер, следуя которым можно попасть из 1 в 5:

a) {1, 4}, {4, 5};

b) {1, 2}, {2, 4}, {4, 5};

c) {1, 4}, {4, 2}, {2, 1}, {1, 4}, {4, 5}.

В одной последовательности ребра повторяются, в другой - не повторяются. Можно указать маршрут (последовательность) от 1 до 5, содержащий все вершины графа. Таков, например, маршрут:

{1, 2}, {2, 4}, {4, 3}, {3, 1}, {1, 4}, {4, 5}

Но не всякую последовательность ребер называют путем.

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

Вершина - начало пути, вершина - конец.

Путь от до называется простым, если он не проходит ни через одну из вершин графа более одного раза. Итак, получается, что последовательность с) не является путем, а последовательности а) и b) - простые пути. Из определения следует, что в пути вершины и ребра могут повторяться, т.е. путь может быть самопересекающимся.

Введем теперь понятие цикла в графе.

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

Простой цикл создается функцией cycle().

Ш G:=cycle(8): draw(G);

5. Связность графа

Решим задачу: Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только двумя другими?

Участника этой компании изобразим вершиной графа, а отношение знакомства между двумя участниками - ребром. Изобразим графы, которые могут соответствовать такой компании.

> with(networks):

> G1:=cycle(6): draw(G1);

Ш G2:=void(6): addedge([{1, 2}, {2, 3}, {3, 1}, {4, 5}, {5, 6}, {6, 4}], G2): draw(G2);

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

Во втором случае получились две отдельные части, не сцепленные между собой ребрами. Такой граф называется несвязным, а "части" - компонентами связности. Каждая компонента представляет собой связный граф. Дадим теперь определения связности вершин в графе и связности графа. Две вершины А и В графа называются связными, если в графе существует путь с концами А и В. Две вершины А и В графа называются несвязными, если в графе не существует ни одного пути, связывающего их.

Например, на рис.2 вершины 1 и 2 - связные, а вершины 1 и 6 - несвязные. Граф называется связным, если каждые две его вершины связные. Граф называется несвязным, если хотя бы две его вершины несвязные. Функция components() находит компоненты связности графа, выводя списки всех ребер каждой компоненты:

> components(G2);

Ш G3:=void(9): connect({1}, {2, 6, 4}, G3): connect({5}, {9, 8}, G3): components(G3); draw(G3);

Рассмотрим операцию удаления ребра из графа, которая осуществляется функцией delete().

При удалении ребра {А,В} из графа G получается граф с теми же вершинами, что и граф G, и всеми ребрами, кроме ребра {А,В}.

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

Ребро {А,В} называется мостом графа G , если в графе, полученном после удаления из G ребра {А,В}, вершины А и В оказываются несвязными.

6. Виды графов

Рассмотрим еще несколько наиболее известных видов графов. Граф, у которого все вершины имеют одну и ту же степень r, называется регулярным графом (или граф, регулярный степени r). Например, на рис.1 - кубический граф, а на рис.2 (см ниже) - граф, регулярный степени 4.

> with(networks):

> G:=void(4): connect({1}, {2, 3, 4}, G): addedge(Cycle(2, 3, 4), G): draw(Linear([4], [1, 3], [2]), G);

Ш H:=void(5): connect({1}, {2, 3, 4, 5}, H): connect({2}, {3, 4, 5}, H): addedge(Cycle(3, 4, 5), H): draw(H);

Известным примером кубического графа является так называемый граф Петерсона, показанный на рис.3. Для этого очень известного графа существует даже специальная функция - petersen(). Заметим, что графы одинаковой степени регулярности могут быть совершенно разными (см. рис.1 и 3).

Ш P:=petersen(): draw(P);

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

Ш Tetr:=tetrahedron(): draw(Tetr);

Ш C:=cube(3): draw(Concentric([0, 1, 3, 2], [4, 5, 7, 6]), C);

> Oct:=octahedron(): draw(Concentric([1, 2, 0, 3, 4, 5]), Oct);

Ш Dod:=dodecahedron(): draw(Concentric([0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13, 14], [15, 16, 17, 18, 19]), Dod);

> Ico:=icosahedron(): draw(Ico);

Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества и так, что каждое ребро в G соединяет какую-нибудь вершину из с какой-либо вершиной из, тогда G называется двудольным графом. На рис.1 показан двудольный граф, у которого ={1, 3, 5} и ={2, 4}.

> with(networks):

> G:=void(5): addedge(Path(1, 2, 3, 4, 5), G): draw(Linear([1, 3, 5], [2, 4]), G);

Если вершины двудольного графа раскрасить двумя цветами, скажем, красным и синим, то любое его ребро имеет один конец красный, а другой - синий. Следует подчеркнуть, что в двудольном графе совсем не обязательно, чтобы каждая вершина из была соединена с каждой вершиной из; если же это так, то он называется полным двудольным графом и обозначается (m и n - число вершин в и). На рис.2 изображен граф:

Ш H:=void(7): connect({1}, {4, 5, 6, 7}, H): connect({2},{4,5,6,7},H): connect({3}, {4, 5, 6, 7}, H): draw(Linear([3, 2, 1], [7, 6, 5, 4]), H);

Ш J:=void(6): connect({1}, {4, 5, 6}, J): connect({2}, {4, 5, 6}, J): connect({3}, {4, 5, 6}, J): draw(Linear([3, 2, 1], [6, 5, 4]), J);

Полный двудольный граф вида называется звездным графом (см. рис.4 - граф).

Ш L:=void(6): connect({1}, {2, 3, 4, 5, 6}, L): draw(Concentric([1], [2, 3, 4, 5, 6]), L);

В теории графов важную роль играют плоские графы.

Граф G называют плоским (или планарным), если его можно нарисовать на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины. Задача определения планарности, например, встречается при разводке печатных плат, где ребра графа - печатные проводники, вершины - контактные площадки. В Maple V проверить планарность графа можно при помощи команды isplanar(), которая возвращает true - если граф планарный и false - в противном случае. Вначале isplanar() упрощает граф, т.е. удаляет циклы и повторяющиеся ребра, а затем граф проверяется на планарность (упростить граф можно при помощи gsimp()).

Ш G:=complete(5): draw(G); isplanar(G);

Ш G1:=complete(3): draw(G1); isplanar(G1);

Эйлерова характеристика графа

Докажем следующее утверждение: Для любого дерева G, имеющего В вершин и Р ребер, справедливо соотношение:

В-Р=1 (1)

Проведем индукцию по числу ребер Р.

1) Р=1 - дерево имеет 1 ребро и 2 вершины: 2-1=1. Соотношение (1) справедливо.

2) Предположим, что для любого дерева, имеющего n ребер, соотношение (1) уже доказано.

3) Пусть G - дерево, имеющее n+1 ребро. G - связен, значит его можно получить из некоторого связного графа G' добавлением одного ребра b. G' содержит n ребер и тоже не содержит циклов, т.е. является деревом. По предположению индукции для G' отношение (1) справедливо, поэтому в G' имеется n+1 вершина. Заметим теперь, что только один конец добавленного ребра b является вершиной G' (иначе, взяв в G' простую последовательность ребер, соединяющую вершины А и В, и, добавив к этой цепочке ребро b, мы получим цикл в G). Следовательно, при добавлении b в G появляется одно новое ребро и одна вершина. Поэтому для графа G справедлива формула.

B-P=n+2-(n+1)=n+2-n-1=1

Таким образом, для любого дерева отношение (1) справедливо. Утверждение доказано.

Разность В-Р, где В - число вершин, а Р - число ребер графа G, называется эйлеровой характеристикой графа и обозначается

(G)=B-P.

Проверим на примере справедливость того, что эйлерова характеристика любого дерева равна 1:

> with(networks):

> F:=void(6): connect({1}, {2, 3, 4}, F): connect({2}, {5, 6}, F): draw(Linear([1], [4, 3, 2], [6, 5]), F);

> p:=nops(vertices(F)) - nops(edges(F));

Граф G (на рис.2) имеет два цикла, причем один цикл содержит внутри себя другой цикл. Ребро {5,6} в этом случае называют перегородкой, т.к. оно соединяет эти циклы.

> N:=void(8): addedge(Cycle(1, 2, 3, 4, 5), N): addedge(Cycle(6, 7, 8), N): addedge({5, 6}, N): draw(Concentric([7, 8, 6], [3, 2, 1, 5, 4]), N);

У плоского графа G гранью называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов (граф G на рис.1 не имеет грани). В качестве грани можно рассматривать и часть плоскости, расположенную "вне" плоского представления графа; она ограничена "изнутри" простым циклом и не содержит в себе других циклов. Эту часть плоскости называют бесконечной гранью. На рис.3 бесконечная грань закрашена зеленым цветом.

Интересные факты: Для всякого плоского представления связного плоского графа без перегородок число вершин В, число ребер Р и число граней с учетом бесконечной Г связаны соотношением:

В-Р+Г=2

Полученную формулу называют формулой Эйлера.

Эйлеровы графы

Исторически топология и теория графов зародились при решении Эйлером задачи о Кенигсбергских мостах. Ее решение мы рассмотрим ниже. В результате решения этой задачи появился еще один вид графов - эйлеровы графы. Эйлеровым путем в графе называется путь, содержащий все ребра графа (т.е. проходящий по каждому ребру ровно по одному разу, но не обязательно замкнутый). Эйлеровым циклом в графе называется цикл, содержащий все ребра графа (т.е. это замкнутый эйлеров путь). Граф, обладающий эйлеровым циклом, называется эйлеровым графом. Интересные факты: В связном графе G существует эйлеров путь тогда и только тогда, когда не более двух его вершин имеют нечетную степень. Граф G является эйлеровым тогда и только тогда, когда он связен и степени всех его вершин четны. Таким образом, замкнутую фигуру, в которой все вершины четные, можно начертить одним росчерком без повторений, начиная обводить ее с любой точки. Подобное задание часто встречается в сборниках занимательных задач и головоломок. Например, на рис.1 изображена птица. Взяв за вершины графа точки пересечения линии, получим три вершины, только две из которых имеют нечетную степень. Поэтому в этом графе существует эйлеров путь, а значит, его (т.е. птицу) можно нарисовать одним росчерком.

Рассмотрим теперь знаменитую задачу о Кенигсбергских мостах. Задача формулируется следующим образом. Мосты через реку Прегель расположены как на рис.2. Вопрос состоит в том, можно ли, прогуливаясь по городу, пройти через каждый мост точно по одному разу и вернуться обратно. Рассмотрим граф, соответствующий схеме мостов. Полностью увидеть этот граф с помощью функции draw() мы не можем, т.к. в графе есть кратные ребра. Чтобы ответить на вопрос задачи, достаточно выяснить, является ли граф эйлеровым. Найдем степени всех вершин получившегося графа.

> with(networks): G:=void(4): connect({1}, {2, 3, 4}, G): connect({4}, {2, 3}, G): connect({1}, {2, 3}, G): degreeseq(G);

Ответ - нет, т.к. степени вершин его нечетны, поэтому нельзя, прогуливаясь по городу, пройти по одному разу все мосты и вернуться обратно. Решим еще одну задачу. На рис.4 изображена решетка. Можно ли провести непрерывную линию, пересекающую точно по разу каждую сторону решетки?

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

Таким образом, к каждой такой точке добавится по 8 ребер. Эти линии будут означать "выход" непрерывной линии за пределы решетки. Таким образом, задача сводится к отысканию эйлерова пути в полученном графе. Создадим этот граф и выведем список степеней всех его вершин.

> M:=void(14): connect({1}, {2, 3, 4, 5, 6, 7, 8, 9, 10}, M): connect({2}, {3, 4, 5, 6, 7, 8, 9, 10}, M): connect({3}, {4, 5, 6, 7, 8, 9, 11}, M): connect({4}, {5, 6, 7, 8, 9, 11}, M): connect({5}, {6, 7, 8, 9, 12}, M): connect({6}, {7, 8, 9, 12}, M): connect({7}, {8, 9, 13}, M): connect({8}, {9, 14}, M): connect({14}, {9, 10, 13}, M): connect({13}, {10, 11, 12}, M): connect({11}, {10, 12}, M): draw(Concentric([12, 11, 10, 14, 13], [5, 4, 3, 2, 1, 9, 8, 7, 6]), M); degreeseq(M);

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

Задача о нахождении кратчайшего пути в графе

Широко распространены задачи нахождения кратчайшего пути. В таких задачах задается граф (сеть дорог) и начальная вершина (пункт отправления). Каждому ребру можно присвоить вес - длина дороги. Кроме этого, ребра могут быть как ориентированными, так и не ориентированными. Задача нахождения кратчайшего пути решается с помощью алгоритма Дейкстры. Результат работы алгоритма - дерево с началом в начальной вершине, причем ко всем остальным вершинам идут кратчайшие пути. В Maple V задачу нахождения кратчайшего пути можно решить при помощи команды shortpathtree().

В следующем примере создадим полный граф с четырьмя вершинами, причем вес каждого ребра равен 1 (по умолчанию):

> G:=complete(4): draw(G);

Получим граф G1 из графа G, применив команду shortpathtree():

Ш G1:=shortpathtree(G, 2): draw(G1);

Таким образом, G1 - дерево, полученное в результате работы алгоритма Дейкстры. Очевидно, что из вершины 2 в вершину 1 быстрее всего можно попасть по ребру {2,1}.

Теперь изменим исходный граф G: ребру, которое соединяет вершины 2 и 3 присвоим вес, равный 100. Мы удалим ребро {2,3} (вес которого по умолчанию равен 1) и восстановим его с весом 100:

> d:=edges({2, 3}, G): delete(d[1], G): addedge({2, 3}, weights=100, G):

> H:=shortpathtree(G, 2): draw(H);

Таким образом, в измененном графе найдены новые кратчайшие пути ко всем вершинам из вершины 2.

Команда shortpathtree() присваивает длины кратчайших путей весам вершин. Воспользуемся этим и с помощью следующей команды получим информацию о расстояниях от вершины 2 до вершин 1, 2, 3, 4:

> vweight(H);

Из данной таблицы видно, что для того, чтобы попасть из вершины 2 в вершину 3, требуется пройти расстояние равное двум (т.е. два ребра с единичными весами).

Лабиринты

Рассмотрим задачу о поиске выхода из лабиринта, коридоры которого не обязательно находятся на одном уровне. Подобная ситуация возникает, например, при блуждании в пещерах или катакомбах. Отождествив коридоры лабиринта с ребрами, а перекрестки, тупики, входы и выходы - с вершинами, мы придем к связному графу, представляющему схему лабиринта. На рис.1 изображен интересный пример лабиринта в саду Хемптон Корт:

Построим соответствующий ему граф.

Ш L:=void(13): addedge(Path(2, 1, 3, 4, 7, 8, 9, 11, 12), L): connect({10}, {7, 8, 9}, L): addedge({13, 11}, L): addedge({3, 5}, L): addedge({4, 6}, L): draw(Linear([1, 4, 3], [2, 6, 5], [13, 7], [10], [12, 8], [11, 9]), L);

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

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

Алгоритм: Условимся, что можно каким-то образом отмечать, в каком направлении пройден данный коридор и какой коридор приводит на данный перекресток в первый раз. Пусть мы находимся на перекрестке а, тогда поиск выхода (или перекрестка b) из лабиринта может быть описан следующим алгоритмом:

1. Никогда не проходить по одному и тому же коридору в одном и том же направлении дважды. 2. Находясь на некотором перекрестке, не выбирать коридора, который привел на этот перекресток в первый раз, если только есть возможность другого выбора.

Мы можем найти выход с помощью функции нахождения кратчайших путей shortpathtree() (см. лабораторную работу № 13). Найдем в графе, изображенном на рис.1, путь от входа в лабиринт (вершина 1) в центр лабиринта (вершина 13).

Ш G:=shortpathtree(L, 1): draw(Linear([1, 4, 3], [2, 6, 5], [13, 7], [10], [12, 8], [11, 9]), G);

Теперь хорошо видно, что в центр лабиринта можно попасть, следуя по следующим вершинам:

1 - 4 - 7 - 10 - 9 - 11 - 12 - 13.

И, соответственно, выйти из центра лабиринта по маршруту:

13 - 12 - 11 - 9 - 10 - 7 - 4 - 1.

7. Деревья, лес

Решим следующую задачу:

Лист бумаги разрезают на три части. Некоторые из полученных листов также разрезаются на три части. Несколько новых листиков вновь разрезают на три более мелкие части и т.д. Сколько получится листиков бумаги, если разрезают k листов?

Решение. Листы бумаги обозначим вершинами графа. Причем количество всех вершин не будет совпадать с количеством получившихся листочков. Ответ мы получим, если будем считать вершины, от которых далее не отходит ни одного ребра (т.е. часть листа не разрезается дальше).

Очевидно (см. Рис.1 ниже), что при разрезании одного листика на три части число листиков увеличивается на два (появляются три новых вместо одного):

> G1:=void(4): connect({1}, {2, 3, 4}, G1): draw(G1);

Если же разрезать k листов, то образуется 1+2k листов:

Ш G2:=void(16): connect({1}, {2, 3, 4}, G2): connect({2}, {5, 6, 7}, G2): connect({4}, {8, 9, 10}, G2): connect({6}, {11, 12, 13}, G2): connect({12}, {14, 15, 16}, G2): draw(Linear([1], [4, 3, 2], [10, 9, 8, 7, 6, 5], [13, 12, 11], [16, 15, 14]), G2);

Кстати, вам не кажется, что схемы на рис.1 и 2 напоминают ветку дерева с листочками? Математики, обратив внимание на это сходство, назвали такие схемы "деревьями".

Дадим определение дерева.

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

Интересные факты: Граф, состоящий из изолированной вершины, тоже является деревом. Дерево обладает минимальным количеством ребер: n-1. Т.е., если удалить любое ребро из дерева, то мы нарушим связность графа. Если к дереву добавить любое новое ребро, мы получим ровно один цикл.

Как решить рассмотренную выше задачу, если мы возьмем два листочка?

Решение. Ответ очевиден: если мы будем один лист разрезать на k частей, а другой лист - на t частей, то всего листочков получится

1+2k+1+2t=2(1+k+t)

Продемонстрируем это:

> with(networks):

> G3:=void(32): connect({1}, {2, 3, 4}, G3): connect({2}, {5, 6, 7}, G3): connect({4}, {8, 9, 10}, G3): connect({6}, {11, 12, 13}, G3): connect({12}, {14, 15, 16}, G3): connect({17}, {18, 19, 20}, G3): connect({18}, {21, 22, 23}, G3): connect({20}, {24, 25, 26}, G3): connect({22}, {27, 28, 29}, G3): connect({28}, {30, 31, 32}, G3): draw(Linear([1], [4, 3, 2], [10, 9, 8, 7, 6, 5], [13, 12, 11], [16, 15, 14], [17], [20, 19, 18], [26, 25, 24, 23, 22, 21], [29, 28, 27], [32, 31, 30]), G3);

Полученный граф немного сложней, чем граф на рис.2. Он состоит из двух деревьев. Такую схему называют "лесом".

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

Интересные факты: В любом лесу с n вершинами и k компонентами n-k ребер.

8. Матрицы графов

При большом числе вершин и ребер рисунок графа теряет наглядность. В таких случаях для задания графов и работы с ними используются таблицы специального вида, называемые матрицами. Матрицей порядка m на n называется таблица из элементов, расположенных в m строках и n столбцах.

Например, в следующей матрице 3 строки и 4 столбца, т.е. 12 элементов: Строки нумеруются сверху вниз, а столбцы - слева направо. Каждому элементу матрицы присваиваются два индекса: первый индекс указывает на номер строки, которой принадлежит элемент, второй - на номер соответствующего столбца. Опишем граф с пятью вершинами, изображенный на рис.1. Для этого каждой вершине поставим в соответствие строку и столбец с одинаковым номером. При этом =1, если ребро {, } принадлежит графу G, и =0, если ребро не принадлежит. Такая матрица называется матрицей смежности графа G.

Считается она функцией adjacency(). Найдем матрицу смежности для графа, изображенного на рис.1:

Ш with(networks): G:=void(5): connect({1}, {2, 3}, G): addedge({2, 5}, G): draw(G);

> adjacency(G);

Если ребра графа ориентированные, то =1, если ребро [,] принадлежит графу (т.е. оно выходит из вершины), и,если ребро [,] либо не принадлежит графу, либо входит в вершину.

> addedge([1, 5], G): K:=adjacency(G);

Всякий граф можно задать матрицей смежности.

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

Кроме матрицы смежности существует матрица инцидентности графа.

Если каждой вершине поставить в соответствие строку, а каждому ребру - столбец с одинаковым номером. При этом =1, если вершина инцидентна (принадлежит) ребру, =0 в противном случае. Такая матрица называется матрицей инцидентности графа G.

Когда ребро ориентированное: если ребро выходит из вершины, то, а, если входит - и, если не принадлежит графу, то =0.

Считается матрица инцидентности функцией incidence(). Найдем матрицу инцидентности для графа, изображенного на рис.1.

> T:=incidence(G);

Сумма чисел, стоящих в любом из столбцов, равна степени вершины, соответствующей выбранному столбцу. Что можно сказать о сумме чисел, стоящих в любой из строк?

Заключение

В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Теория графов рассматривается как одна из ветвей топологии; непосредственное отношение она имеет также к алгебре и к теории чисел. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач, нахождении максимального потока в сети, кратчайшего расстояния, максимального паросочетания, проверки планарности графа и др. Как особый класс можно выделить задачи оптимизации на графах. Математические развлечения и головоломки тоже являются частью теории графов, например, знаменитая проблема четырех красок, интригующая математиков и по сей день. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей.

Литература

1. Басакер Р., Саати Т., Конечные графы и сети, М., Наука, 1974.

2. Белов В.В., Воробьев Е.М., Шаталов В.Е., Теория графов, М., Наука,1976.

3. Берж К., Теория графов и ее применения, М., ИЛ,1962.

4. Березина Л.Ю., Графы и их применение, М., Просвещение, 1976.

5. Болтянский В.Г., Наглядная топология, М., Просвещение, 1982.

6. Домодряд А.П., Математические игры и развлечения, М., Физматгиз, 1961.

7. Дынкин Е.Б., Успенский В.А., Математические беседы, М., Физматгиз, 1961.

8. Зыков А.А., Теория конечных графов, Новосибирск, Наука, 1968.

9. Кордемский Б.А., Математическая смекалка, М., Физматгиз, 1954. 10. Кук Д., Бейз Г., Компьютерная математика, М., Наука, 1990.

11. Оре О., Графы и их применение, Новокузнецкий Физико-математический институт, 2000.

12. Оре О., Теория графов, М., Наука, 1968.

13. Прохоров Г.В., Леденев М.А., Колбеев В.В., Пакет символьных вычислений Maple V.

14. Рауз Белл М., Математические развлечения и очерки, London-New York.,1962.

15. Татт У., Теория графов, М., Наука, 1977.

16. Уилсон Р., Введение в теорию графов, М., Мир, 1977. 17. Харрари Ф., Теория графов, М., Мир, 1973.