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

UptoLike

ВУЗ: 

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

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

Рубрика: 

16
2B1.2. Матричные способы задания графов
Для алгебраического задания графов исполь-
зуются матрицы смежности и инцидентности.
Определение 1.17. Матрица смежности A = (a
ij
)
определяется одинаково для ориентированного и
неориентированного графов. Это квадратная мат-
рица порядка n, где n – число вершин, у которой
a
ij
=
1, ( , ) ,
0, ( , ) .
ij
ij
если xx A
если xx A
∈
⎧
⎪
⎨
∉
⎪
⎩
Пример 1.5.
Матрица смежности графа, изображенного
на рис. 2, имеет вид:
A =
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠
.
Пример 1.6.
Матрица смежности ориентированного гра-
фа, изображенного на рис. 3, имеет вид:
A =
0 1 1 0
0 0 0 0
0 1 0 1
0 0 0 0
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠
.
161
32. Какая модель теории графов адекватна сле-
дующей задаче: Имеется сеть связи, соединяющая
n узлов. Если выйдут из строя некоторые каналы,
то связь между узлами может быть нарушена. Ка-
кие каналы можно удалить без нарушения связи?
Какие каналы нужно удалить, чтобы связь не на-
рушалась, а общая стоимость всех каналов была
минимальной?
33. Какая модель теории графов адекватна сле-
дующей задаче: Разрабатывается проект газопро-
вода, соединяющего буровые скважины в Мекси-
канском заливе с находящейся на берегу приемной
станцией. Следует выбрать проект, в котором
строительство газопровода имеет минимальную
стоимость.
34. Какая модель теории графов адекватна сле-
дующей задаче: Пусть имеется n изолированных
городов. Какое
минимальное количество дорог
между некоторыми городами надо построить, что-
бы иметь возможность попасть из любого города в
любой другой? Если заданы расстояния между го-
родами, то как выбрать сеть дорог с минимальной
общей длиной? 
   1.2. Матричные способы задания графов
   2B                                              32. Какая модель теории графов адекватна сле-
      Для алгебраического задания графов исполь-   дующей задаче: Имеется сеть связи, соединяющая
зуются матрицы смежности и инцидентности.          n узлов. Если выйдут из строя некоторые каналы,
Определение 1.17. Матрица смежности A = (aij)      то связь между узлами может быть нарушена. Ка-
определяется одинаково для ориентированного и      кие каналы можно удалить без нарушения связи?
неориентированного графов. Это квадратная мат-     Какие каналы нужно удалить, чтобы связь не на-
рица порядка n, где n – число вершин, у которой    рушалась, а общая стоимость всех каналов была
                                                   минимальной?
                    ⎧1, если ( xi , x j ) ∈ A,
             aij = ⎪⎨
                                                   33. Какая модель теории графов адекватна сле-
                    ⎪⎩0, если ( xi , x j ) ∉ A.    дующей задаче: Разрабатывается проект газопро-
                                                   вода, соединяющего буровые скважины в Мекси-
                    Пример 1.5.                    канском заливе с находящейся на берегу приемной
      Матрица смежности графа, изображенного       станцией. Следует выбрать проект, в котором
на рис. 2, имеет вид:                              строительство газопровода имеет минимальную
                                                   стоимость.
                    ⎛0      1 1 0⎞                 34. Какая модель теории графов адекватна сле-
                    ⎜       0 1 0 ⎟⎟ .
                A = ⎜1                             дующей задаче: Пусть имеется n изолированных
                    ⎜1      1 0 1⎟                 городов. Какое минимальное количество дорог
                    ⎜              ⎟
                    ⎝0      0 1 0⎠                 между некоторыми городами надо построить, что-
                                                   бы иметь возможность попасть из любого города в
                     Пример 1.6.                   любой другой? Если заданы расстояния между го-
      Матрица смежности ориентированного гра-      родами, то как выбрать сеть дорог с минимальной
фа, изображенного на рис. 3, имеет вид:            общей длиной?
                      ⎛0    1 1 0⎞
                      ⎜0    0 0 0 ⎟⎟ .
                A=    ⎜
                      ⎜0    1 0 1⎟
                      ⎜            ⎟
                      ⎝0    0 0 0⎠



                               16                                          161

Страницы