Основные понятия теории графов. Гладких О.Б - 17 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

Составители: 

Рубрика: 

160
26. Постройте дерево наименьшей общей длины,
ребра которого соединяют вершины правильного
шестиугольника.
27. Сколько компонент связности может иметь де-
рево?
28. Можно ли построить дерево, все вершины ко-
торого имеют степень больше, чем единица?
29. Какая модель теории графов адекватна сле-
дующей задаче: Различные организации x
1
, ... , x
n
обмениваются некоторой информацией (при этом
связи могут быть направленными). Если между
организациями x
i
и x
j
возможен непосредственный
обмен информацией, то затраты на него составля-
ют r
ij
рублей. Возможен ли обмен информацией
между двумя организациями? Если возможен, то
как осуществить этот обмен с наименьшими затра-
тами?
30. Какая модель теории графов адекватна сле-
дующей задаче: Имеется схема городских дорог с
перекрестками и, возможно, односторонним дви-
жением. Необходимо найти маршрут, соединяю-
щий две точки на карте. Как найти такой
маршрут
при условии, что его длина минимальна?
31. Какая модель теории графов адекватна сле-
дующей задаче: Требуется построить схему элек-
трической сети, в которой клеммы должны быть
соединены с помощью проводов наименьшей об-
щей длины.
17
Матрица смежности полностью задает граф.
Определение 1.18. Матрицей инцидентности B =
= (b
ij
) ориентированного графа называется прямо-
угольная матрица (n
× m), где n – число вершин, m
– число ребер, у которой
b
i
=
1, если вершина является началом дуги ;
1, если вершина является концом дуги ;
0, если вершина не инцидентна дуге ;
ij
ij
ij
x
a
x
a
xa
⎧
⎪
−
⎨
⎪
⎩
Для неориентированного графа матрица ин-
цидентности B задается следующим образом:
b
i
=
1, если вершина инцидентна ребру ;
0, если вершина не инцидентна ребру .
ij
ij
xa
x
a
⎧
⎪
⎨
⎪
⎩
Пример 1.7.
Матрица инцидентности графа, изображен-
ного на рис. 2, имеет вид:
B =
1 0 1 0
1 1 0 0
0 1 1 1
0 0 0 1
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠
.
Пример 1.8.
Матрица инцидентности ориентированного
графа, изображенного на рис. 3, имеет вид: 
26. Постройте дерево наименьшей общей длины,               Матрица смежности полностью задает граф.
ребра которого соединяют вершины правильного        Определение 1.18. Матрицей инцидентности B =
шестиугольника.                                     = (bij) ориентированного графа называется прямо-
27. Сколько компонент связности может иметь де-     угольная матрица (n × m), где n – число вершин, m
рево?                                               – число ребер, у которой
28. Можно ли построить дерево, все вершины ко-
торого имеют степень больше, чем единица?                   ⎧ 1, если вершина xi является началом дуги a j ;
29. Какая модель теории графов адекватна сле-         bi = ⎪⎨−1, если вершина xi является концом дуги a j ;
дующей задаче: Различные организации x1, ... , xn           ⎪
                                                            ⎩ 0, если вершина xi не инцидентна дуге a j ;
обмениваются некоторой информацией (при этом
связи могут быть направленными). Если между              Для неориентированного графа матрица ин-
организациями xi и xj возможен непосредственный     цидентности B задается следующим образом:
обмен информацией, то затраты на него составля-
                                                             ⎧1, если вершина xi инцидентна ребру a j ;
ют rij рублей. Возможен ли обмен информацией           bi = ⎪⎨
между двумя организациями? Если возможен, то                ⎪⎩0, если вершина xi не инцидентна ребру a j .
как осуществить этот обмен с наименьшими затра-
тами?                                                                   Пример 1.7.
30. Какая модель теории графов адекватна сле-             Матрица инцидентности графа, изображен-
дующей задаче: Имеется схема городских дорог с      ного на рис. 2, имеет вид:
перекрестками и, возможно, односторонним дви-
                                                                            ⎛1 0 1 0 ⎞
жением. Необходимо найти маршрут, соединяю-                            B=   ⎜1 1 0 0 ⎟ .
щий две точки на карте. Как найти такой маршрут                             ⎜        ⎟
                                                                            ⎜ 0 1 1 1⎟
при условии, что его длина минимальна?                                      ⎜        ⎟
                                                                            ⎝ 0 0 0 1⎠
31. Какая модель теории графов адекватна сле-
дующей задаче: Требуется построить схему элек-                        Пример 1.8.
трической сети, в которой клеммы должны быть              Матрица инцидентности ориентированного
соединены с помощью проводов наименьшей об-         графа, изображенного на рис. 3, имеет вид:
щей длины.

                         160                                                       17

Страницы