Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Задача 12

Читайте также:
  1. В. (гневно): Так зачем вы взялись лечить нас, если заняты своими задачами?
  2. Ваша задача - не жалея ярких красок напомнить ему о его прошлых
  3. Вложені цикли в матричних задачах
  4. Вывод очевиден: мужская косметика должна отличаться от женской не только запахом или упаковкой, но и теми задачами, с которыми ей предстоит справиться.
  5. ГЛАВА 12. Возвышенная задача — нести Свет
  6. Главная задача Венеры
  7. Главная задача Марса-Юпитера

Взвешенный граф задан матрицей весов. Построить его графическое представление, с помощью алгоритма Дейкстры определить матрицу расстояний. Найти радиус, центр и диаметр графа.

 

 

Изобразим данный граф:

 

Над каждым ребром подпишем его вес

 

 

 

Определим матрицу расстояний для данного графа:

 

 
  0+1=1 0+2=2 0+2+3=5 0+2+2=4 0+2=2
0+2=2   0+2+2=4 0+2+3=5 0+2+3=5 0+1=1
0+2=2 0+2+2=4   0+3=3 0+3+3=6 0+2+2=4
0+3+2=5 0+3+2=5 0+3=3   0+3=3 0+3+2+1=6
0+2+2=4 0+2+3=5 0+3+3=6 0+3=3   0+2+1=3
0+2=2 0+1=1 0+2+2=4 0+3+2+1=6 0+2+1=3  

 

 

Определим для каждой вершины графа наибольшее удаление:

 

, , , , ,

 

Минимальное из полученных чисел является радиусом графа, а максимальное – диаметром:

 

,

 

Центрами являются вершины и

 

Заказать контрольную работу по дискретной математике и не только Вы можете у нас на сайте http://otl.su

 

Также посетите нашу группу Вконтакте: http://vk.com/otlsu

 

OTL.SU – Быстро, качественно, доступно!

 


Дата добавления: 2015-10-13; просмотров: 90 | Нарушение авторских прав


Читайте в этой же книге: Задача 2 | Задача 3 | Задача 5 | Задача 10 |
<== предыдущая страница | следующая страница ==>
Задача 11| Контрольная работа №2

mybiblioteka.su - 2015-2024 год. (0.007 сек.)