4.3. Методы представления графов в аналитической форме кратко

Привет, Вы узнаете о том , что такое графов в аналитической форме, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое графов в аналитической форме, теория графов , настоятельно рекомендую прочитать все из категории Теория конечных автоматов.

Рассмотрим пример построения графа. Пусть множество вершин определено, как V = {a, b, c, d}, а множество ребер, как X = {1, 2, 3, …, 7}. Пусть инцидентор графа Р определен девятью значениями: P (a,1,a); P (a,2,b); P (b,3,a); P (a,3,b); P (a,4,c); P (a,5,c); P (c,5,a); P (c,6, b); P (b, 7,c) – которые истинны, остальные ложны. Изображение графа представлено на рис. 4.8. В данном примере вершины а, b, и с – смежные, а вершина d – изолированная, т.е. не инцидентна ни одному ребру.

1

2

а

3 b

4 5

6

7

d

c

Рис. 4.8

Существуют и другие способы задания графов. Рассмотрим еще один пример: пусть задано изображение неориентированного графа G (рис. 4.9а) и подобного ему орграфа GО (рис. 4.9б). Пусть v1, v2, ... v5 – вершины, а х1, х2, ... х6 – ребра (дуги). Графы G и GО можно представить в аналитической форме либо матрицей смежности A, либо матрицей инцидентности B.

v4 х2 v3 v4 х2 v3

х3 х5 х3 х5

х1 v2 х4 х1 v2 х4

v5 х6 v5 х6

v1 v1

а) б)

Рис. 4.9

Матрицей инцидентности графа G называется матрица B = ||bij||, имеющая i=1, .., n столбцов и j = 1, ..., m строк, что соответствует количеству вершин n и количеству ребер m. Элемент матрицы bij = 1, если вершина vi инцидентна ребру х j, и bij = 0, если не инцидентна. Об этом говорит сайт https://intellect.icu . Для ориентированного графа элемент матрицы bij = 1, если дуга исходит из вершины, и bij = –1, если дуга заходит в вершину. Если в орграфе есть петля, то bij = 2. Для неориентированного графа и орграфа, представленных на рис. 4.9а и б, матрицы инцидентности выглядят соответственно следующим образом:

v1, v2, v3, v4, v5 v1, v2, v3, v4, v5

1 1 0 0 0 х1 1 -1 0 0 0 х1

0 1 1 0 0 х2 0 1 -1 0 0 х2

B(G) = 0 1 1 0 0 х3 B(GО) = 0 -1 1 0 0 х3

0 1 0 0 1 х4 0 1 0 0 -1 х4

0 0 1 0 1 х5 0 0 -1 0 1 х5

0 0 0 0 1 х6 0 0 0 0 2 х6

В каждой строке матрицы инцидентности только два элемента (или один) отличны от нуля. По матрице инцидентности можно определить степени всех вершин графа. При этом для петель значение удваивается.

Матрицей смежности графа G называется квадратная матрица A=||aij||, столбцам и строкам которой соответствуют вершины графа i=1,...,n; j = 1, ..., n. Для неориентированного графа элемент матрицы aij равен числу ребер, инцидентных вершинам vi и vj, для орграфа – количеству ребер с началом в вершине vi и концом в вершине vj. Для нашего примера матрицы смежности будут

v1, v2, v3, v4, v5 v1, v2, v3, v4, v5

0 1 0 0 0 v1 0 0 0 0 0 v1

1 0 2 0 1 v2 1 0 1 0 0 v2

A(G) = 0 2 0 0 1 v3 A(GО) = 0 1 0 0 1 v3

0 0 0 0 0 v4 0 0 0 0 0 v4

0 1 1 0 1 v5 0 1 0 0 1 v5

Как видно, матрица смежности для неориентированного графа симметрична, а для орграфа – необязательно. Орграф с симметричной матрицей смежности канонически соответствует неорграфу с такой же матрицей смежности.

Итак, графы могут быть заданы тремя способами:

1. Непосредственным заданием множеств вершин V и ребер X , а также отношением инцидентности.

2. Матрицей смежности или матрицей инцидентности.

3. Графическим изображением (рисунком).

Как определить, что данные два графа одинаковы? Для первых двух способов задания ответ прост: когда совпадают их описания – списки вершин и ребер или матрицы. По рисунку определить, одинаковы ли графы, сложнее. Один и тот же граф можно изобразить разными рисунками (рис. 4.10), по-разному расположив вершины и придав ребрам разную геометрическую форму и длину. С другой стороны, два одинаковых, на первый взгляд, рисунка могут задавать разные графы, если у них различная нумерация вершин, из-за чего матрицы смежности и списки ребер у них будут различны (рис. 4.11).

Рис. 4.10 Рис. 4.11

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

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