2.2. Основные термины и определения теории графов
Таким образом, граф, в общем виде, можно записать как 0(Х,И).
Граф у которого число вершин и ребер конечно называется конечным графом.
Наглядно граф представляется в виде некоторого рисунка (рис. 3), в котором вершины обозначаются точкой хі - элемент множества X. Каждое ребро представляется в виде линии, соединяющей между собой вершины Хі и Хр.
Х={Хі,Х2,Х3,Х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
Матрица смежности для неориентированного графа является симметричной относительно главной диагонали.
Еще по теме 2.2. Основные термины и определения теории графов:
- Основные термины и их определения, принятые в аудите
- § 1. Определение. Типология.Основные современные теории конфликта
- 4.1.2. Основные понятия и определения теории интеллектуальных информационных систем
- 1.10.Термины и определения
- ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ ПО АУДИТУ
- 4.1.1. Основные термины и понятия
- Основные термины и понятия
- Основные термины и понятия
- Основные термины и понятия
- Основные термины и понятия
- Основные термины и понятия
- Основные термины и понятия