Алгоритмы на графах и их приложения. Дорофеева В.И. - 6 стр.

UptoLike

ВУЗ: 

ОГУ | Орел

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

Рубрика: 

6
Граф может быть графически представлен диаграммой, на которой узлам
соответствуют точки плоскости, а каждая дуга (n
i
, n
j
) изображается стрелкой,
направленной из точки n
i
в точку n
j
. Так на рисунке 1 граф представлен че-
тырьмя узлами n
1
–n
4
и шестью дугами (n
1
, n
2
), (n
1
, n
4
), (n
2
, n
4
), (n
3
, n
2
), (n
4
, n
1
) и
(n
4
, n
3
).
Многие физические структуры удобно представить в виде графа такого
рода (например, систему городских улиц, если каждую улицу с двухсторонним
движением рассматривать как пару дуг с одинаковыми конечными узлами, но с
противоположной ориентацией).
Будем говорить, что на графе G=(N, A) дуга (n
i
, n
j
) направлена от n
i
к n
j
, а
точки n
i
и n
j
называть соответственно начальным и конечным узлом дуги (n
i
, n
j
).
Последовательность дуг, в которой конечный узел каждой дуги является в то
же время начальным узлом следующей дуги, называется путем. Так на графе,
представленном на рисунке 1, последовательность (n
1
, n
2
), (n
2
, n
4
), (n
4
, n
3
) – путь
из n
1
в n
3
.
Для графов также существует такое понятие, как изоморфизм. Понятие
изоморфизма для графов имеет наглядное толкование. Представим рёбра гра-
фов эластичными нитями, связывающими узлы – вершины. Тогда, изоморфизм
можно представить как перемещение узлов и растяжение нитей.
1
4
2
3
Рисунок 1 
       Граф может быть графически представлен диаграммой, на которой узлам
соответствуют точки плоскости, а каждая дуга (ni, nj) изображается стрелкой,
направленной из точки ni в точку nj. Так на рисунке 1 граф представлен че-
тырьмя узлами n1–n4 и шестью дугами (n1, n2), (n1, n4), (n2, n4), (n3, n2), (n4, n1) и
(n4, n3).

                                          1




                       4                                      2




                                              3

              Рисунок 1
       Многие физические структуры удобно представить в виде графа такого
рода (например, систему городских улиц, если каждую улицу с двухсторонним
движением рассматривать как пару дуг с одинаковыми конечными узлами, но с
противоположной ориентацией).
       Будем говорить, что на графе G=(N, A) дуга (ni, nj) направлена от ni к nj, а
точки ni и nj называть соответственно начальным и конечным узлом дуги (ni, nj).
Последовательность дуг, в которой конечный узел каждой дуги является в то
же время начальным узлом следующей дуги, называется путем. Так на графе,
представленном на рисунке 1, последовательность (n1, n2), (n2, n4), (n4, n3) – путь
из n1 в n3.
       Для графов также существует такое понятие, как изоморфизм. Понятие
изоморфизма для графов имеет наглядное толкование. Представим рёбра гра-
фов эластичными нитями, связывающими узлы – вершины. Тогда, изоморфизм
можно представить как перемещение узлов и растяжение нитей.



                                                  6

Страницы