41.Способы задания графов.

Способы задания графов:

Графический способ

Задание графа при помощи матрицы инцидентности

nm – где n кол-во вершин графа, m – кол-во ребер графа. По вертикали и горизонтали указываются вершины и ребра, а на пересечении i-строки и j-столбца, если ребро i инцидентно вершине j ставим 1 и 0 в противном случае.

В случае орграфа

В петле присваивается любое другое число!!! (чаще всего 2)

Списком ребер графа

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

Если граф имеет изолированные вершины, то они помещаются в конец списка.

Матричный способ:

Матрица смежности - это квадратная матрица размера, гдеn – кол-во вершин графа.

В случае n-графа проставляется число ребер соединяющих эти две вершины.

В случае ор-графа проставляется кол-во дуг имеющих начало в вершине и конец в вершине.

Определение 2.21. Матрицей смежности конечного графа G с p вершинами называется матрица A(G)=||a_ij|| (i, j = 1, 2, …, p), в которой если смежны вершины то ставим 1, иначе 0.

42. Действия над графами.

Граф H будем называть частью графа G(), если мн-воV(H) и мн-во ребер E(H) содержится в соответствующих мн-вах для графа G: и.

Граф H называется суграфом графа G, если он является частью графа G и кол-во вершин графа H равно кол-ву вершин графа G, т.е.V(H)=V(G).

Граф G() назыв.подграфом графа G(V), если граф G() содержит все ребра, которые инцидентны вершинам из мн-ва.

Определим некоторые операции на графах:

1. Удаление или добавление ребра.

2. Удаление вершины. Из множества вершин удаляем выбранную вершину, а из множества ребер все инцидентные ей ребра.

3. Стягивание ребра. Отождествляем (стягиваем) вершины инцидентные выбранному ребру.

4. Добавление вершины (разбиение ребра). Выберем некоторое ребро (u,v) из множества ребер и удалим его. В множество вершин добавим новую вершину w, а в множество ребер новые ребра (u,w) и (w,v).

Дополнение части H графа G явл. графом удовлетворяющим след. условиям:

1)=

2)

Операции:

Сумма и

Произведение : и

43. Ориентированные и неориентированные графы.

Графом G называется совокупность 2-х множеств (V, E), где V – множество вершин графа, а Е – множество ребер графа. Между вершинами и ребрами графа G устанавливают отношение инцидентности. Считают, что ребро инцидентно вершинам ,, если оно соединяет эти 2-е вершины. При этом вершины,называютсясмежными. Отношение инцидентности является самым главным элементом графа, т.к. указывает способ объединения множеств V и E в единый объект. Если ребро , соединяющее 2-е вершины, направлено от одной вершины к другой, то оно называетсяориентированным или дугой и графически изображается стрелками, направленными от начала к концу. Граф, содержащий дуги называется ориентированным или орграфом. Граф, не содержащий ни одной дуги (содержащий только ребра) называется неориентированным или н-графом.

Пример.

Н-ГРАФ (Рис.1) ОР-ГРАФ(Рис.2)

Ребра, инцидентные одной и той же паре вершин называются кратными (на рис.1 это ребра 8 и 9).