37.Графы. Основные понятия.

Графом G наз. пара мн-в: G=(V,E). мн-во. V наз. вершин(непустое), а E – рёбер(возможно пустое). Мн-во Е представляет собой некоторое мн-во неупорядоченых пар вершин. Число вершин -р, кол-во ребер — q.

Для описания графа между мн-вом V и E необходимо определить отношение инцидентности, которое определяется если каждому ребру е (е Э Е) поставлена в соответствие вершина v.

Два ребра инцидентны одной вершине назыв смежными.две вершины инцидентны одной вершине назыв смежными. С использованием этих понятий можно описать любой граф однозначно.

Ориентированный граф — если ребра связывающие вершины не равноправны и описывают перемещение от одной вершины к другой в определенном порядке, то на ребре становится стрелка, и граф назыв ориентированным.

Если в графе мн-во ребер явл пустым – то граф пустой.

Ребро, которое начинается и заканчивается в одной и той же вершине — петля.

Кратные ребра — если весто мн-во ребер рассматривается некоторый набор содержащий одинаковые элементы, то эти элементы — кратные ребра, а граф — мультиграф.

Если элементы мн-ва ребер необязательно двухэлементные пары, а некоторые подмножества мн-ва V то такие элементы — гипердуги, а граф — гиперграф.

Если задана ф-я F которая вфполняет отображение F: V → M, то мн-во М — мн-во меток, а граф — помеченый.

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

Число рёбер, инцедентных вершине наз. степенью вершины.

Подграфом D графа G (DG) наз. граф, такой, что MN; WU

38 Способы представления графов:

1). Список рёбер (задаётся число вершин и мн-во рёбер, входящих в граф). Объём памяти, необходимый для описания графа не превышает n2 (n – число вершин).

2). Матрица смежности {gij}, n*n. gij={1,(i,j)U;0,(i,j)U;}. Объём памяти <=n2.

3. Матрица инцедентности: {dij}, n*m. Предварительно рёбра нумеруютсяот 1 до m. dij=1, если вершина i инцедентна ребру j и dij=0 в противном случае. Объём памяти n*m<n3.

38. Способы представления графов

Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над ними. Представление выбирается исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления. Представления иллюстрируются на конкретных примерах графа G(слева) и орграфа(справа) D (см. рис.)

Матрица смежности.

Представление матрицы с помощью квадратной булевской матрицы

М : array [1..p, 1..p] of 0..1,

отражающей смежность вершин, называемой матрицей смежности, где

Пример

Матрица инциденций

Представление графа с помощью матрицы H : array [1..p, 1..q] of 0..1 (для орграфов : array [1..p, 1..q] of -1..1), отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа

столбцы соответсвуют вершинам графа, строки — ребрам.

Для ориентированного графа: 1 – если вершина инцидентна ребру и является его концом

0 – если вершина и ребро неинцидентны

-1 – если вершина инцидентна ребру и является его началом

Пример

Список смежности.(в конспекте не было, но пусть останется на всякий случай=))

Представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей Г : array [1..p] of N на списки смежных вершин (элемент списка представлен структурой N : record v : 1..p; n: N end record) называется списком смежности.

Пример

Массив дуг.(тоже не было, но пусть будет=)

Представление графа с помощью массива структур E : array [1..p] of record b, e : 1..p endrecord, отражающего список смежных вершин, называется массивом ребер (для орграфов – массивом дуг).

Пример

Список ребер (более эффективный):

строка соотв ребру, и в ней хранится ин-фа о соотв этому ребру вершине. Для неориентированиого графа порядок не важен, для орграфа — упорядочен.(нач — кон.)

39. Идентификация графов заданых своими представлениями. Граф может быть представлен различными способами. Он может быть задан рисунком, матрицей инцидентности, списком рёбер или матрицей смежности. Вид чертежа зависит от формы линий и взаимного расположения вершин. Иногда, даже для пары достаточно простых графов, непонятно, одинаковы ли они. Вид матриц см инц , также как списков рёбер зависит от нумерации вершин и рёбер графа.

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

Опр. Графы G1(V1, E1) и G2(V2, E2) называются изоморфными, если существует взаимно однозначное отображение j: V1 ® V2, сохраняющее смежность.

Перенумерация вершин графа задаётся строкой новых номеров вершин a1, a2, ...an, расположенных в исходном порядке. Новая матрица смежности получается из исходной матрицы перемещением каждого элемента Еij в ai строку, в  aj столбец. Поэтому, чтобы узнать, представляют ли две таблицы смежности изоморфные графы, можно, например, перевести всевозможные одинаковые перестановки строк и столбцов первой матрицы. В результате перестановок a1, a2, ...an строк и столбцов будем получать новые матрицы. Если одна из таких перестановок даст матрицу, тожественно совпадающую со второй матрицей, то представляемые ими графы изоморфны. Для выполнения этой проверки в общем случае надо выполнить п! Перестановок.