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

Страницы работы

25 страниц (Word-файл)

Содержание работы

1. ОПРЕДЕЛЕНИЯ, ФОРМЫ ПРЕДСТАВЛЕНИЯ ГРАФОВ

Граф G  задается множеством точек или вершин х1, х2,…хn (которое обозначим через Х) и множеством отрезков а1, а2,…аn (которое обозначим символом А) соединяющих между собой все или часть этих точек. Математически граф G полностью задается парой (Х, А): G = (Х, А).

Если отрезки из множества А ориентированы, что обычно показывается стрелками в геометрическом представлении графа, то они называются дугами, а граф называется ориентированным графом (орграфом) (рис.1.1). Если отрезки не имеют ориентации, то они называются ребрами, а граф –  неориентированным (рис. 1.2).

Часто употребляется другое, аналитическое описание орграфа [2]. Задается множество вершин Х и соответствие Г, которое показывает, как связаны между собой эти вершины. Соответствие Г называют отображением множества Х в Х, а граф тогда обозначается парой G = (Х, Г). Соответствие Г(хi) – множество таких вершин хj Î Х, для которых в графе G существует дуга (хi, хj). Дуга, отображающая вершину в саму себя, называется петлей (дуга а4 на рис.1.1). Например, для вершин х1, х2, х6 графа рис. 1.1  имеем :

Г(х1) = {х5, х6},

Г(х2) = {х2, х4},

Г(х6) = Æ

Соответствие Г-1i) называют обратным (инверсным) соответствием, понимая под ним множество вершин хк Î Х, для которых в G cуществует дуга (хк, хi). Для графа рис.1.1 Г-11) = {х5}, Г-12) = {х23},Г-16)={х15}.

В случае неориентированного графа или смешанного (содержащего и т.д. и дуги, и ребра) предполагается, что соответствие Г задает такой эквивалентный орграф, который получается из исходного заменой каждого ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Так, для вершин х1 и х2 графа на рис.1.2 имеем:

Г(х1) = Г-1 1) = {х2, х4, х5};  Г(х2) = Г-12)  = {х1, х3, х5}.

Отображение Г множества вершин Хк = {х1, х2,..., хк} есть объединение отображений этих вершин:

Г(Хк) = Г(х1) U Г(х2) U...U Г(хк).

Например, для графа рис. 1.1 Г({х1, х2, х6} ) = {х2, х4, х5, х6}; Г({х3, х4, х5}) = {х1, х2, х3,х4, х6 }.

Матричное представление графов осуществляется в виде матриц смежности и инциденций (инцидентности).

Две вершины хi и xj являются смежными, если есть дуга (ребро), соединяющая обе вершины. Дуга a называется инцидентной вершине х, если заходит в эту вершину или исходит из нее, и вершина х называется инцидентной такой дуге а.

          Матрица смежности А = [aij] орграфа G(Х, А) с n вершинами имеет размерность n ´ n и определяется следующим образом:

Матрица смежности для орграфа, изображенного на рис. 1.1, представлена на рис. 1.3.

   

Рис. 1.3                                                            Рис. 1.4

Для неориентированного графа матрица смежности определяется так:

 

 
1, если вершины xi  и xj смежные,

0, в противном случае, т.е. матрица смежности неориентированного графа всегда симметрична. Матрица смежности графа рис. 1.2 представлена на рис. 1.5.

     Рис. 1.5

Матрица инциденций В = [bij]  орграфа G(Х, А) с n вершинами и m дугами имеет размерность n x m и определяется так:

 
1, если хi является начальной вершиной дуги аj,

-1, если хi является конечной вершиной дуги аj,

0, если аj не инцидентнах хi начальной вершиной дуги аj.

Матрица инциденций для графа рис. 1.1 представлена на рис. 1.4. Для неориентированного графа матрица инциденций составляется так же, как и для орграфа, только все элементы, равные –1, заменяются на +1. Для графа рис.1.2 матрица инциденций приведена на рис. 1.6.

Рис. 1.6

Степень d вершины xi  неориентированного графа есть число ребер, инцидентных этой вершине. Для графа рис. 1.2

d(x1) = d(x2) = d(x3) = d(x4) = 3;  d(x5) = 4.

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

Упражнения

1. Чему равна сумма элементов i-й строки в матрице смежности орграфа , i – го столбца?

2.  Изменится ли матрица смежности орграфа, если пренебречь ориентацией дуг?

3.Что представляет собой  матрица инциденций неориентированного графа:  сумма элементов i-й  строки, i-го столбца?

4. Неориентированный  граф  G(X, A) задан матрицей смежности А.

Привести геометрическое и аналитическое представление графа, построить матрицу инциденций.

5. Чему равна сумма степеней всех вершин неориентированного графа?

6. Что определяет сумма полустепеней исхода всех вершин орграфа, сумма полустепеней захода?

7. Доказать, что в неориентированном графе число вершин с нечетной степенью четно (нуль – четное число).

8. Можно ли из полного графа с 17 вершинами удалить некоторые ребра так, чтобы степень каждой вершины равнялась пяти?

2.ЧАСТИ ГРАФОВ

Граф G¢(X,¢ A¢) называется частью графа G(X, A), если Х¢ Í Х, А.

Рассмотрим два вида частей: подграф (порожденный подграф) и суграф (остовный подграф).

Подграфом G графа  G(Х, Г) называется граф (Хs, Гs), в который входит лишь часть вершин графа G, образующих множество Хs, вместе с дугами, соединяющими эти вершины, т.е. Хs Ì Х и для каждой вершины хi Î Хs Гsi) = Г(хi) Õ Хs

Похожие материалы

Информация о работе