Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 73 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

3. Построить базу относительно вершины x3 для предыдущего графа. Решение
представить таблицей.
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
10
∞ ∞
0
+
∞ ∞ ∞ ∞
∞ ∞ ∞
14 19 6 6 5
+
8
∞ ∞ ∞
. .
5.5. Орциклы и циклы
Особую группу составляют замкнутые пути. Путь а
1
, а
2
,...,a
q
называется
замкнутым, если в нем начальная вершина а
1
и конечная вершина а
q
совпадают.
Так, например, для графа на рис. 32. можно составить несколько замкнутых путей:
М
1
: а
3
, а
6
,а
11
М
2
: а
11
, а
3
, а
4
, а
7
, а
1
, а
12
, а
9
М
3
: а
3
, а
4
, а
7
, а
10
, а
9
, а
11
Пути М
1
и М
3
являются замкнутыми простыми орцепями, называемыми
контурами или простыми орциклами. Поскольку в них одна и та же вершина
используется только один раз (за исключением начальной и конечной). Путь М
2
не
является контуром, так как вершина х
1
используется в нем дважды. 
3. Построить базу относительно вершины x3 для предыдущего графа. Решение
представить таблицей.
x1      x2         x3        x4          x5    x6      x7   x8     x9      x10
∞       ∞          0+        ∞           ∞     ∞       ∞    ∞      ∞       ∞
14      19                   6           6     5+      8    ∞      ∞       ∞




.                                                                                .
                                     5.5. Орциклы и циклы
      Особую группу составляют замкнутые пути. Путь а1, а2,...,aq называется
замкнутым, если в нем начальная вершина а1 и конечная вершина аq совпадают.
Так, например, для графа на рис. 32. можно составить несколько замкнутых путей:
      М1: а3, а6,а11
      М2: а11, а3, а4, а7, а1, а12, а9
      М3: а3, а4, а7, а10, а9, а11
      Пути М1 и М3 являются замкнутыми простыми орцепями, называемыми
контурами или простыми орциклами. Поскольку в них одна и та же вершина
используется только один раз (за исключением начальной и конечной). Путь М2 не
является контуром, так как вершина х1 используется в нем дважды.

Страницы