Задачи, платформа съдържание
№9 диграфа даден близост матрица. трябва да:
а) да се направи графиката;
б) разпределя силно свързани компоненти;
в) заместване на всички дъги в ребрата и получената ненасочена графиката, за да открие Ойлер верига (или линии).
а) се направи графика.
Матрицата близост графика (диграфа) - е квадратна матрица с размер, така че за всеки елемент в ия ред и jth колона е 1, ако тата и тата върховете свързани с ръба (дъга, започвайки от върха), и е 0 друго случай.
-- 1, ако горната и - свързани (в продължение на диграфа дъга преминава от в) 0 в противен случай.
Съгласно тази конструкция насочен графика.
б) Изберете компонентите на силна връзка.
Компоненти силно свързани диграфа - е неговата максимална свързан подграфи. Концепцията на силна връзка разбира, както следва: от всеки връх на подграф е начин за останалата част от върховете на подграф и обратно, другите върховете на подграф е начинът на върха на този подграф. Това се нарича подграф компонент силно свързан диграфът.
За да се изолира силно свързан компонент като алгоритъм на базата диграфа използва метод за търсене в дълбочина. влизане Търсене в дълбочина в примера с лекция. За опростяване на обозначението, ще означаваме горната част на фигурата.
Започваме от най-богатия 1.
От един връх байпас е завършена.
Да започнем с 2 върхове.
От 2 върхове байпас е завършена.
Започваме с 6 върхове.
В резултат на това, последователност на върховете: 1,4,2,5,3,6.
От първа дълбочина протокола за обиск, показва, че постижимо от 1 4 (), и от 4 достижим 1 (). Вижда се също така, че два постижимо 3 и 5 () 2, 3 и 5 са постижими () и 2 от 5 е постижима (). Така идентифицираните две силно свързани компоненти (1,4) и (1,3,5). Или пишете по друг начин: Двата компонента на силна връзка и. Дебела дъга показва компонентите на силна връзка.
в) Замяна на всички ръбове и ребра в получения ненасочена графиката, за да открие Ойлер верига (или линии).
За да намерите Ойлер веригата в свързан граф, който има пикове само дори власт, да се използва алгоритъма Фльори:
1) движение започва от произволно връх; Ние сме по ръбовете, включително ръбовете във веригата Euler и изваждането им от графиката.
2) След като в началото на избрания от провлака пътя, само ако няма начин чрез цикъла.
3) Ако графиката са ребрата, които не могат да се използват за продължаване на съществуващия път, трябва да започнете да се изгради проста затворен контур на вече завършената горния и ръбове инцидента с него, ако последният не е бил използван преди това.
Строителство може да започне от всеки край на графиката. Тъй като ние се получи цикъл:
В този случай, след като сме получили Ойлер верига. Ръбът е провлак (мост).
№10 претеглени графика матрични определени дължини дъга. Начертайте графика. Намерете: а) минимално тегло обхваща дърво;
б) най-краткия разстояние от върха на други върховете V3 графика, използвайки алгоритъм на Dijkstra на.
Равен графика с помощта на правилото:
Това означава, че в точката на пресичане на редове и колони съдържа дължината на дъга или безкрайността ако не дъги (ръбове) между съответните върхове.
а) Намерете обхваща дървото минимално тегло.
За да намерите минималната Kruskal isplzuem теглото този алгоритъм.
Изграждане на ядрото ще започне до край с минимално тегло.
Как да се присъедините към ребрата на ядрото:
В горната част изберете от които не са свързани с ребро ръбове по-малко тегло и я прикрепете към ядрото.
В горната част на трите ребра не са свързани с една и съща две най-малкото тегло, изберете ръба и я прикрепете към ядрото. Присъединяването на ребра не представлява линия.
Горната Избрано за които не са свързани краища на реброто с най-малката тежест и я прикрепете към ядрото. Присъединяването на ребра не представлява линия.
В първите две не са оставени свързани ръбове. Изборът на реброто с най-малката тежест, когато се присъедини към ядрото, цикълът не се образува.
Чрез добавяне на всеки от оставащите ръбове воля цикъл.
Всички ръбове се считат, алгоритъмът е завършен.
Skeleton подчерта удебелени ръбове.
б) Намерете най-късото разстояние от върха на останалите върхове v3 графика, като използвате Алгоритъм на Дейкстра.
Tops доставят бележките, и графиката ще присъства етикет все още не е намерен на пътя.
Върхове, които ще станат постоянни, изберете знака.
Vertex А е станала постоянна, а с нея и съседната В, С и F разстоянието намерено за тях (е 1, 5 и 3) е изместен на етикета (1, А), (5, А) и (3, А)
Минимални разстояния от един връх на V (1 А) става постоянни.
Изчислява разстоянието от него, на свързани с нея С, D и Е. разстояние С за 1 + 1 = 2 е по-малко от ток (5) етикет връх С се променя на (2, В).
Разстоянието, което се F 1 + 2 = 3 е равна на текущата (3) върховете F на етикета не се променят и неговата константа.
Разстояние до връх D е по-малко върховете на етикета се променя на (4, B).
От всички текущи етикети C (2, B) разстояния на върха прави постоянни.
С Разстояние от върха към съседния връх Е е по-малко от етикета на връх се заменя с (4 С).
От време върхове от горния връх В Г (4, В) става постоянна.
Разстояние от временна връх Е чрез връх С 5 + 4 = 9 чрез връх D 3 + 4 + 1 = 8, връх F 1 + 3 = 4, минималното разстояние е връх F 1 + 3 = 4 етикет промени върховете Е до (1 F) и става постоянна.
Най-късото разстояние от върха, са отбелязани удебелени ръбове.
Най-късото разстояние от върха:
1 = 1 в началото на пътя;
2. горната = 2, пътека;
3 = 3 в началото на пътя;
= 4 до топ 5, пътя;
5. горната = 4, пътя.