Информационные модели на графах

Взвешенный граф

• Взвешенный граф — это граф, в котором с вершинами или линиями связана дополнительная информация.
• Эта информация называется весом вершины или линии.

Взвешенный граф

• На рисунке изображен взвешенный граф, представляющий информацию о дорогах между четырьмя деревнями. Веса вершин — названия деревень, веса линий — длина дорог в километрах.
• И те, и другие задаются надписями.

Дерево

• Дерево — это граф, предназначенный для отображения таких связей между объектами как вложенность, подчиненность, наследование и т.п.
• Сначала рисуем «главную» вершину, которая не зависит ни от одной другой вершины. Эта вершина называется корнем дерева и является единственной вершиной «1го уровня».
• Далее добавляем вершины «2го уровня».
• На каждом шаге добавляем вершины очередного уровня, каждая из которых будет связана ровно с одной вершиной предыдущего уровня и не будет иметь никаких иных связей

Дерево

• Дерево ориентировано, причем дуги направлены от верхних вершин к нижним.
• Верхняя вершина называется предком для связанных с ней нижних вершин
• Нижние вершины — потомками соответствующей верхней вершины.
• На любом дереве существует единственная вершина, не имеющая предка, — корень — и может быть сколько угодно вершин, не имеющих потомков, — листьев.
• Все остальные вершины имеют ровно одного предка и сколько угодно потомков

Родословное дерево первых русских князей

Задания 3. Формальные описания реальных объектов и процессов http://inf.sdamgia.ru/test?theme=3

• Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

• Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

• По таблице построим граф

• A

• B

• C

• D

• E

• 0

• 1

• 2

• 2

• 7

• 3

• 4

• Свяжем с каждой вершиной маркер, длина пути от А
• Длина пути из А в А =0
• Маркер вершины В равен маркеру вершины А + длина пути от А до В = 0+1=1
• Вершина А больше ни с чем не связана. Исключим её из рассмотрения
• Маркер С=1+2=3
• Маркер D=1+2=3
• Маркер Е=1+7=8
• Исключим вершину B
• C связана с E
• Маркер Е=3+3=6 найден путь короче
• Исключим С
• Из D в E есть путь
• Маркер E= 3+4=7 больше

• A

• B

• C

• D

• E

• 0

• 1

• 2

• 2

• 7

• 3

• 4

• 1

• 3

• 3

• 8

• 6

• 7

• Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

• Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

• По таблице построим граф

• A

• B

• C

• D

• E

• 5

• 3

• 1

• 4

• 6

• 1

• A

• B

• C

• D

• E

• 0

• 5

• 3

• 1

• 4

• 6

• 1

• 5

• 3

• 9

• 9

• 6

• 4

• 8

• A

• B

• C

• D

• E

• 0

• 2

• 5

• 3

• 1

• 7

• 2

• 7

• 5

• 8

• 6

• 2

• 12

• По графу найдите путь из А в Е