Графом G= (X,U) будем называть совокупность двух конечных множеств; множества вершин X={x,…x} и множества ребер (дуг) U={u…. u}, состоящего из некоторых пар элементов (x,x) множества X. Геометрически граф может быть представлен в виде рисунка, в котором вершинам соответствуют точки, а ребрам линии, соединяющие все или некоторые из этих точек. Граф называется помеченным, если его вершинам приписаны некоторые метки, например номера.

Если пары вершин (x,x) в множестве U являются неупорядоченными (т.е., порядок соединения вершин несущественен), то граф называется неориентированным (неорграфом), а пары (x,x) - ребрами этого графа (рисунок 1).

Размещено на http://www.allbest.ru/

Рисунок 1

дискретная математика ориентированный граф

При этом вершины x,x называют концами (концевыми вершинами) ребра. В данном случае также говорят, что ребро (x,x) - соединяет вершины xи x.

Если пары вершин (x,x) в множестве U являются упорядоченными (т.е., порядок соединения вершин существенен), то граф называется ориентированным (орграфом), а пары (x,x) - дугами (рисунок 2).

Размещено на http://www.allbest.ru/

Рисунок 2

При этом x - начало (начальная вершина) дуги, x - конец (конечная вершина) дуги. Говорят также, что дуга <x, x> исходит из вершины xи заходит в вершину x. Заметим, что <x, x> и <x, x> - это различные дуги в графе. При изображении орграфа дуги обозначаются стрелками, указывающими их ориентацию (направление). Пара вершин (x,x) в графе может соединяться двумя или более ребрами (дугами одного направления).

Отметим, что любой неориентированный граф можно представить в виде орграфа путем замены каждого его ребра двумя противоположно направленными дугами. [1]

Иногда дугам графа G сопоставляются (приписываются) числа - дуге (x,x) ставится в соответствие некоторое число с, называемое весом, или длиной, или стоимостью (ценой) дуги. Тогда граф G называется графом со взвешенным дугами. Иногда веса (числа v) приписываются вершинам x графа, и тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным.

Петлей называется дуга, начальная и конечна вершины которой совпадают. Примером петли является дуга u на рисунке 1. [2]

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

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

Замкнутая цепь называется циклом, замкнутая простая цепь - простым циклом. Замкнутый путь называется контуром, замкнутый простой путь - простым контуром. Граф, не содержащий циклов, называют ациклическим.

Число дуг, исходящих из вершины x ориентированного графа, называется полустепенью исхода вершины x и обозначается (x). Число дуг, заходящих в вершину x, называется полустепенью захода вершины x и обозначается (x). [1]

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

Рисунок 3 - Граф G

Матрицей смежности неориентированного графа G= (X,U) с n вершинами называется квадратная матрица А порядка n, элементы которой определяются следующим образом:

Для ориентированного графа:

Следовательно, матрица смежности графа, изображенного на рисунку 3 имеет вид, в противном случае

Рисунок 4 - Матрица смежности графа G

Петлям в матрице смежности соответствуют элементы, расположенные на главной диагонали. Матрица смежности полностью определяет структуру графа. Например, сумма всех элементов строки x матрицы дает полустепень исхода вершины x, а сумма элементов столбца x - полустепень захода вершины x. Множество столбцов, имеющих 1 в строке x, есть множество Г (x), а множество строк, которые имеют 1 в столбце x, совпадает с множеством Г (x). [2]

1.2 Компьютерные средства для реализации задачи