18. Опред-е графа. Матрицы смежностей и инциденций. Методы хранения графов в памяти эвм.

Графом назыв-ся пара множ-в Г=[А,В], где А – любое непустое множ-во, а В – множ-во, кот-е явл-ся подмножеством множ-ва V(A). Матрицей смежности M порядка n назыв-ся матрица, сост-я из чисел m_ij, равных сумме чисел ориентиров-х ребер, идущих из а_i в а_j (или чисел неориентированных ребер, соединяющих эти вершины)

Эта матрица симметричная. #. b₁ = (1,2); b₂ = (1,3); b₃ = (1,4); b₄ = (1,5); b₅ = (2,3); b₆ = (3,4).

	0	1	1	1	1
	1	0	1	0	0
М =	1	1	0	1	0
	1	0	1	0	0
	1	0	0	0	0

Другой вариант матричного представления — матрица инциденций является классическим способом в теории графов. Это не экономичный способ задания.

Данная матрица зависит от того как занумерованы ребра. #. b₁ = (1,2); b₂ = (1,3); b₃ = (1,4); b₄ = (1,5); b₅ = (2,3); b₆ = (3,4). i=5; j=6.

1	1	1	1	0	0
1	0	0	0	1	0
0	1	0	0	1	1
0	0	1	0	0	1
0	0	0	1	0	0

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

19. Путь в графе и связные комп-ты графа. Цепи, простые цепи, циклы, простые циклы. Операции удал-я вершины, уд-я ребра. Дерево и его особ-ти.

Графом называется пара множеств Г=[А,В], где А – любое непустое множество, а В – множество, которое является подмножеством множества V(A). Элементы из А называются вершинами графа, а элементы из В – его ребрами. Например, А={1,2,3,4,5}, В={(1,2),(2,3),(3,4),(1,5),(1,4),(3,1)}. Неупорядоченная пара вершин – ребро, а упорядоченная пара – дуга. Путем в графе Г называется такая последовательность дуг, в которой конец каждой последующей дуги совпадает с началом предыдущей. Длиной пути называют число входящих в этот путь дуг. Путь может быть конечным и бесконечным. Путь, в котором никакая дуга не встречается дважды, называется элементарным. Подграф содержит подмножество вершин графа и все соединяющие их рёбра. Компонента связности – максимально связанный подграф. Путь без повтор-ся ребер наз-ся цепью, а цепь без повтор-ся вершин называется простой. Цепь, в кот-й совпадают концевые вершины наз-ся циклом, а цикл, в кто-м нет повто-х вершин, кроме концевых, наз-ся простым. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги – ориентированным или орграфом. Граф называется петлей, если его начало и конец совпадают. Удаление ребра. Г=[А,В] и a  А, b  В. Удалить ребро b это значит построить новый граф Г`=[А` ,В`],

в кот-м А`=А, В`=В\b

Удаление вершин. Г=[А,В] и a  А, чтобы удалить вершину а из Г=[А,В] нужно, построить граф новый Г`=[А` ,В`], в кот-м А`=А\{a}, В` получится из В удал-е все ребра. (а будет на пересечении)

Д ерево – это граф без циклов. Граф называется связным, если для любых двух вершин существует путь, соединяющий эти вершины. (первый явл., а второй не явл.). Если Г=[А,В] явл. Деревом и число его вершин = р, то о числе ребер можно сказать совершенно опред-но: в дереве имеется еще одна особенность любые две вершины в дереве связаны и при этом единственной простой цепью.