поддержка
проекта:
разместите на своей странице нашу кнопку!И мы
разместим на нашей странице Вашу кнопку или ссылку. Заявку прислать на
e-mail
код нашей кнопки:
Граф
Граф - совокупность точек и линий, в которой каждая линия соединяет
две точки. Точки называются вершинами графа, линии - ребрами графа. Если
ребро соединяет две вершины, то говорят, что оно им инцидентно; вершины,
соединенные ребром, называются смежными. Две вершины, соединяемые
ребром, могут совпадать; такое ребро называется петлей. Число ребер,
инцидентных вершине, называется степенью вершины. Если два ребра
инцидентны одной и той же паре вершин, они называются кратными; граф,
содержащий кратные ребра, называется мультиграфом.
Граф 1 содержит четыре вершины {1, 2, 3, 4} и семь ребер
{а, b, с, d, е, f,
g} (рис. 1). Ребро а инцидентно вершинам 2 и
4; ребро g инцидентно только вершине 3 и является петлей, вершины 2 и 3
смежны, а вершины 1 и 4 не смежны; ребра d и f-
кратные; степень вершины 2 равна 4.
Ребро, соединяющее две вершины, может иметь направление от одной вершины
к другой; в этом случае оно называется направленным или ориентированным
и изображается стрелкой. Граф, в котором все ребра - ориентированные,
называется ориентированным графом (орграфом); ребра орграфа часто
называют дугами. Дуги именуются кратными, если они не только имеют общие
вершины, но и совпадают по направлению. Граф 2 - ориентированный; дуги d
и f - кратные (рис. 2).
Граф однозначно задан, если заданы множество его вершин, множество ребер
и указаны все инцидентности (т. е. указано, какие вершины какими ребрами
соединены). Наиболее наглядно граф задается рисунком; однако не все
детали рисунка одинаково важны; в частности, несущественны
геометрические свойства ребер (длина, кривизна и т. д.) и взаимное
расположение вершин на плоскости. Для машинной обработки более удобны
символические представления графов, в которых несущественных
геометрических деталей нет, например представление графа списками вершин
и ребер. Граф 1 задается списком вершин {1, 2, 3, 4} и списком ребер, в
котором для каждого ребра указана пара инцидентных ему вершин:
Такой же список ребер имеет и граф 3; поэтому графы 1 и
3 равны, хотя их рисунки заметно отличаются (рис. 3).
Для неориентированного ребра порядок, в котором указаны соединяемые им
вершины, неважен. Для ориентированного ребра это важно: первой
указывается вершина, из которой выходит ребро. Например, орграф 2
получен из графа 1 введением ориентации ребер; однако, для того чтобы
приведенный выше список ребер описывал граф 2, в нем нужно изменить
описание ребер с и d - с: (3, 2) и d: (4, 2).
Граф может вовсе не иметь ребер; тогда он состоит из изолированных
вершин и называется пустым. Если в неориентированном графе с п вершинами
нет кратных ребер и петель, то максимальное число ребер в нем равно
n*(n-1)/2 -Это
соответствует случаю, когда между любыми двумя вершинами есть ребро;
такой граф называется полным.
Маршрут - это последовательность ребер в неориентированном графе, в
котором конец каждого ребра совпадает с началом следующего ребра. Число
ребер маршрута называется его длиной. Цикл - это замкнутый маршрут, т.
е. маршрут, в котором начальная вершина совпадает с конечной. В графе 1
а, с, е - маршрут; а, f, е, b - цикл. В
орграфе ориентированный маршрут, т. е. маршрут, в котором все дуги
проходятся по их ориентации, называется путем, а путь, являющийся
циклом, называется ориентированным циклом. В графе 2 а, d, е - путь,
f, е, с - ориентированный цикл. Иногда в
литературе используется и другая терминология: например, замкнутый
маршрут именуют контуром, а циклом называют только такой контур, который
не пересекает сам себя, т. е. не содержит повторяющихся вершин.
Неориентированный граф называется связным, если между любыми двумя его
вершинами есть маршрут. Орграф считается связным, если он связан без
учета ориентации его дуг. Связный граф с п вершинами содержит не менее п
- 1 ребер. Орграф называется сильно связным, если из любой вершины в
любую другую существует путь. Граф 2 - связный, но не сильно связный,
так как в вершину 1 нет путей из других вершин.
Понятие графа благодаря его наглядности и высокой общности служит в
информатике основным средством для описания структуры сложных объектов и
функционирования систем. При описании структур вершинами являются
компоненты объекта, а ребрами - связи между ними (примеры -
вычислительные сети, логические схемы, иерархические структуры). При
описании функционирования вершинам соответствуют состояния системы, а
ребрам - переходы между состояниями (примеры - граф переходов автомата;
граф игры, в котором вершины изображают позиции, а дуги - ходы,
переводящие одну позицию в другую). Иногда описание в виде графа
содержит оба эти аспекта. Например, вершины сетевого графика или
блок-схемы алгоритма представляют его компоненты (работы, операторы), а
прохождение по путям изображает передачу активности от одной компоненты
к другой, т. е. процесс функционирования.