<<
>>

2.2. Основные термины и определения теории графов

Понятие графа опирается на основные понятия теории множеств. Содержательно граф может быть представлен в виде двух объектов (множеств): множество вершин Х и множество ребер и, каждая из которых представляет упорядоченную пару из Х.

Таким образом, граф, в общем виде, можно записать как 0(Х,И).

Граф у которого число вершин и ребер конечно называется конечным графом.

Наглядно граф представляется в виде некоторого рисунка (рис. 3), в котором вершины обозначаются точкой хі - элемент множества X. Каждое ребро представляется в виде линии, соединяющей между собой вершины Хі и Хр.

Х={Хі,Х23,Х4,Х5} - множество вершин;

И={(ХІ,Х2), (ХІ,Х5), (ХІ,Х4), (ХІ,ХЗ), (Х2,Х4), (Х2,Х5), (ХЗ,Х5)};

х5 Количество вершин графа

Х2
х,
хз
Рис.
3.
Математическая модель, представленная в виде графа решает две задачи:

- модель является языковым представлением системы, которое воспринимается современными вычислительными средствами;

- все математические свойства модели являются свойствами самой системы, что позволяет применять различные методы и подходы к исследованию системы.

называется мощностью вершин графа и обозначается |х|, |х|=5; Количество ребер графа называется мощностью ребер графа и обозначается |и|, |и|=7;

Мультичисло т=5;

Хі

Рис. 4.

Мультиграф.
Две вершины называются смежными, если существует ребро Иуеи соединяющее эти вершины. (Пример: (х], х2)—и]2 (рис. 3)).

Ребро Иу инцидентно вершинам хІ5 Х| если оно связывает эти вершины. В свою очередь два ребра называются смежными, если существует вершина инцидентная обоим ребрам. (Пример: (х2, х5)= и25 —■ х2, х5; (х2, х5) и (х3, х5) - смежные ребра; (х2, х5) и (х3, х4) - не смежные ребра.)

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

Иногда рассматривают графы, у которых оба конца ребра заканчиваются одной и той же вершине. Такие ребра имеют особое название - петли. (Пример: и22 = 2, х2)).

Матрица смежности. Еще одной формой представления графа является матрица смежности. Элементами ее является количество ребер, соединяющих между собой вершины графа. Матрица смежности является квадратной матрицей.

, где г - количество ребер, соединяющих вершины х^

пх п

я =

х^ п - количество вершин.

Матрица смежности для графа, изображенного на рис. 5 имеет следующий вид:

1 1 2 0 0 1

1 1 0 0 4 1

2 0 0 3 0 0 0 0 3 0 1 4

0 4 0 1 3 0

1 1 0 4 0 1

Матрица смежности для неориентированного графа является симметричной относительно главной диагонали.

<< | >>
Источник: Арапов А.А.. Теория организации и системный анализ - М. - 74 с.. 2003

Еще по теме 2.2. Основные термины и определения теории графов:

  1. Основные термины и их определения, принятые в аудите
  2. § 1. Определение. Типология.Основные современные теории конфликта
  3. 4.1.2. Основные понятия и определения теории интеллектуальных информационных систем
  4. 1.10.Термины и определения
  5. ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ ПО АУДИТУ
  6. 4.1.1. Основные термины и понятия
  7. Основные термины и понятия
  8. Основные термины и понятия
  9. Основные термины и понятия
  10. Основные термины и понятия
  11. Основные термины и понятия
  12. Основные термины и понятия