![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Смежные дуги – это дуги инцидентные одной вершине.
Смежные вершины – вершины, инцидентные одной дуге.
Матрица смежности - это матрица смежных вершин.
Матрица смежности заполняется по следующему правилу: , если из i-той вершины исходит дуга в j – тую вершину; во всех остальных случаях
(для удобства и наглядности на практике в матрице смежности нули не проставляются).
Для графа, представленного на рис. 3.2 матрица смежности имеет вид:
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |
![]() | ||||||
![]() | ||||||
![]() | ||||||
![]() | ||||||
![]() | ||||||
![]() |
Полустепенью захода i–той вершины называется число дуг, заходящих в данную вершину.
Полустепенью исхода i-той вершины называется число дуг, исходящих из данной вершины.
Степенью i-той вершины исхода называется сумма полустепеней захода и исхода:
(3.2)
Свойства матрицы смежности:
1. Сумма единиц по строке определяет полустепень исхода;
2. Сумма единиц по столбцу определяет полустепень захода;
3. Сумма единиц по строкам и по столбцам определяет степень вершин.
Основное свойство графа:
В любых графах число вершин с нечетной степенью четно.
Путем в графе называется последовательность дуг такая, что каждая следующая дуга исходит из вершины, в которую заходит предыдущая дуга.
Длиной пути называется количество пройденных дуг.
Простой путь – это такой путь, в котором дуга встречается не более одного раза.
Элементарный путь – это путь, в котором вершина встречается не более одного раза.
Контур – путь, начинающийся и заканчивающийся в одной точке.
Петля – контур длиной в одну единицу.
Графы бывают двух видов:
· ориентированный граф (орграф) - это граф, состоящий из вершин и дуг.
· неориентированный граф – это граф, состоящий из вершин и ребер. Ребро – это дуга, не имеющая направление.
Рис. 3.3. Неориентированный граф
В неориентированном графе путь называется цепью; контур – циклом.
Неориентированный граф также может быть задан с помощью матриц инцидентности и смежности.
Матрица инцидентности для неориентированного графа составляется по правилу:
· , если i-тая вершина инцидентна j-тому ребру;
· , если i-тая вершина не инцидента j-тому ребру;
· , если. в i-той вершине j-тое ребро образует петлю.
Для графа, представленного на рис. 3.3, матрица инцидентности имеет вид:
I | II | III | IV | V | VI | VII | |
Матрица смежности для неориентированного графа составляется по правилу: , если из i-тая и j – тая вершины смежные.
Для графа, представленного на рис. 3.3, матрица смежности имеет вид:
Матрица смежности для неориентированного графа симметрична относительно главной диагонали. Степень i- той вершины равна сумме элементов по строке или по столбцу матрицы смежности.
Если в графе присутствуют как ребра, так и дуги, то он называется смешанным.
Если между двумя вершинами существует более чем 1 дуга или ребро, то такой граф называется мультиграфом.
![]() |
Рис. 3.4. Смешанный мультиграф.
Граф называется связным, если между любыми двумя вершинами которого существует путь (цепь).
Дата публикования: 2014-11-03; Прочитано: 1000 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!