Teoria grafów. Teoria grafów to rozległa niezależna gałąź matematyki dyskretnej

Korobova Anastasia, uczennica gr. 14-PGS-48D

W dzisiejszych czasach ważne jest, aby się uczyć różne metody, właściwości i niestandardowe zastosowania. Zastanowimy się nad zastosowaniem metody „Wykres” w otaczającej nas rzeczywistości.

Słowo „wykres” w matematyce oznacza obraz, na którym narysowanych jest kilka punktów, z których niektóre są połączone liniami. Przede wszystkim warto powiedzieć, że hrabiowie, o których będziemy rozmawiać, nie mają nic wspólnego z arystokratami z przeszłości. Nasze „wykresy” wywodzą się od greckiego słowa „grapho”, które oznacza „piszę”. Ten sam rdzeń w słowach „wykres”, „biografia”.

Pierwsza praca z teorii grafów należy do Leonharda Eulera i pojawiła się w 1736 roku w publikacjach Petersburskiej Akademii Nauk.

Liczy spełniają:

w fizyce - w budowie obwodów elektrycznych

w chemii i biologii - w badaniu cząsteczek ich łańcuchów

w historii - przy kompilacji drzew genealogicznych (rodowód)

w geografii - w mapowaniu

w geometrii - rysunki wielokątów, wielościanów, figur przestrzennych

w ekonomii - przy rozwiązywaniu problemów wyboru optymalnej ścieżki dla przepływów towarowych (linie lotnicze, metro, koleje)

Teoria grafów jest wykorzystywana w rozwiązywaniu zadań olimpiad matematycznych. Wykresy dają wgląd w warunki problemu, upraszczają rozwiązanie i ujawniają podobieństwo problemów.

Teraz w każdej gałęzi nauki i technologii spotykasz się z wykresami.

Pobierać:

Zapowiedź:

Aby skorzystać z podglądu prezentacji, załóż konto (konto) Google i zaloguj się: https://accounts.google.com

Podpisy slajdów:

Prezentacja z matematyki Temat: „Wykresy” Wypełnia uczeń grupy 14-PGS-48D Korobova Anastasia

Wykres to figura składająca się z punktów i linii łączących te punkty. Linie nazywane są krawędziami wykresu, a punkty są nazywane wierzchołkami. Wierzchołki, z których wyłania się parzysta liczba krawędzi, nazywamy parzystymi, a nieparzystymi – nieparzystymi. Przykłady grafów Teoria grafów

Leonhard Euler (4 kwietnia 1707, Bazylea, Szwajcaria - 7 września 1783, Sankt Petersburg, Imperium Rosyjskie) był matematykiem szwajcarskim, niemieckim i rosyjskim, który wniósł znaczący wkład w rozwój matematyki, a także mechaniki, fizyki, astronomia i szereg nauk stosowanych. Euler jest autorem ponad 800 artykułów z zakresu analizy matematycznej, geometrii różniczkowej, teorii liczb, obliczeń przybliżonych, mechaniki nieba, fizyki matematycznej, optyki, balistyki, przemysłu stoczniowego, teorii muzyki itp.

Figura (wykres), którą można narysować bez podnoszenia ołówka z kartki, nazywa się unicursal. Wzór 1. Wykres, który ma tylko dwa nieparzyste wierzchołki, można narysować bez podnoszenia ołówka z papieru, a ruch musi zaczynać się od jednego z tych nieparzystych wierzchołków i kończyć się na drugim z nich. (Rys. A) Wzór 2 . Wykresu z więcej niż dwoma nieparzystymi wierzchołkami nie można narysować „jednym pociągnięciem” (rys. B) Wykresy Eulera B A

Wzór 3. Jeśli wszystkie wierzchołki wykresu są parzyste, to bez podnoszenia ołówka z kartki, rysując wzdłuż każdej krawędzi tylko raz, narysuj ten wykres. Ruch może rozpocząć się od dowolnego wierzchołka i zakończyć na tym samym wierzchołku.

Od dawna wśród mieszkańców Królewca krążyła taka zagadka: jak przejść przez wszystkie mosty (na rzece Pregoła) bez dwukrotnego przechodzenia przez żaden z nich? Wielu próbowało rozwiązać ten problem, zarówno teoretycznie, jak i praktycznie, podczas spacerów. Problem mostów królewieckich.

Jest to wykres, w którym niektóre krawędzie mogą być skierowane, a niektóre nieskierowane. Liczba mieszana

Wykres ważony 1 2 4 2 3 A B C D E

Drzewo to dowolny połączony graf, który nie ma cykli. Drzewa Drzewa

Jest to (multi)graf, którego krawędziom przypisano kierunek. Krawędzie skierowane są również nazywane łukami. Kierowany wykres

Liczy spełniają:

Teoria grafów jest wykorzystywana w rozwiązywaniu zadań olimpiad matematycznych. Wykresy dają wgląd w warunki problemu, upraszczają rozwiązanie i ujawniają podobieństwo problemów. Teraz w każdej gałęzi nauki i technologii spotykasz się z wykresami.

Dziękuję za uwagę!

zapoznanie studentów z pojęciem „Wykresu”, podstawowymi zasadami jego budowy;

kształtować umiejętność podkreślania relacji łączących obiekty;

rozwijać uwagę, umiejętność logicznego rozumowania;

sprzyjać wzajemnej pomocy, umiejętności pracy w zespole

utrwalenie zdobytej wiedzy w praktyce

rozwój pamięci, uwagi;

rozwój niezależności;

edukacja aktywności poznawczej.

Sprzęt:

• klasa komputerowa wyposażona w nowoczesną technologię, projektor wideo, ekran;
• komputery z systemem operacyjnym Windows XP, program Microsoft Office PowerPoint 2003;
• wyposażenie tablicy (temat lekcji, nowe terminy). Rozdawać.

Plan lekcji.

II. Prezentacja nowego materiału. (10 minut.)

III. Mocowanie materiału. Praktyczna praca. (15-20 min.)

IV. Podsumowanie lekcji (2 min)

v. Praca domowa.

I. Moment organizacyjny. Aktualizacja wiedzy.

Cześć! Nasza lekcja nazywa się „Wykresy”. Zapoznamy się z pojęciem „Wykresów”, nauczymy się je przedstawiać i rozwiązywać problemy na ten temat.

II Prezentacja nowego materiału.

Pierwsza praca nad teorią grafów należy do Leonharda Eulera (1736), chociaż termin „graf” został po raz pierwszy wprowadzony w 1936 roku przez węgierskiego matematyka Denesha Koeniga. Wykresy nazwano schematami składającymi się z punktów i odcinków linii prostych lub krzywych łączących te punkty (przykłady wykresów pokazano na rysunku 1)

Za pomocą wykresów często upraszczano rozwiązywanie problemów formułowanych w różnych dziedzinach wiedzy: w automatyce, elektronice, fizyce, chemii itp. Za pomocą wykresów przedstawiane są schematy dróg, gazociągów, sieci ciepłowniczych i elektroenergetycznych . Wykresy pomagają w rozwiązywaniu problemów matematycznych i ekonomicznych.

Graph – (z greckiego grapho – piszę) jest środkiem wizualnej reprezentacji elementów obiektu połączeń między nimi. To wspaniałe obiekty matematyczne, z ich pomocą można rozwiązać wiele różnych, pozornie niepodobnych do siebie problemów.

Wykres to jakiś model informacyjny

Wykres składa się z wierzchołków lub węzłów połączonych łukami lub segmentami - krawędziami. Linia może być skierowana, tj. mieć strzałkę (łuk), jeśli nie jest skierowana - krawędź. Dwa wierzchołki połączone łukiem lub krawędzią nazywane są sąsiednimi.

Przykłady wykresów (slajd 4, 5, 6)

Zadanie 1 (slajd 7):

Między dziewięcioma planetami Układu Słonecznego została nawiązana komunikacja kosmiczna. Regularne rakiety latają na następujących trasach:

Ziemia - Merkury; Pluton - Wenus; Ziemia - Pluton; Pluton - Merkury; Merkury - Wenus; Uran - Neptun; Neptun - Saturn; Saturn - Jowisz; Jowisz - Mars; Mars - Uran.

Czy można latać zwykłymi rakietami z Ziemi na Marsa?

Rozwiązanie: Narysujmy diagram stanu: planety przedstawimy kropkami, a trasy rakiet liniami.

Teraz od razu wiadomo, że nie można polecieć z Ziemi na Marsa.

Dwa wierzchołki połączone łukiem lub krawędzią nazywane są sąsiednimi. Każda krawędź lub łuk jest powiązany z numerem. Liczba może wskazywać odległość między osiedlami, czas przejścia z jednego szczytu na drugi itp.

Zadanie 2 (slajd 9) - rozwiązanie znajduje się przy tablicy. Masza przyszła do zoo i chce zobaczyć jak najwięcej zwierząt. Którą ścieżką powinna obrać? Żółty, czerwony, zielony?

Zadanie 3 (11 slajd) - rozwiązanie znajdziesz przy tablicy. Pięć drużyn piłkarskich A, B, C, D, E musi rozegrać ze sobą mecze. Zagrał już A z B, C, D; B c A, C, D. ile meczów rozegrano do tej pory? Ile zostało do grania?

Reprezentacja graficzna (slajd 12)

Wykres można przedstawić jako listę łuków (AB; 7), graficznie lub za pomocą tabeli.

Listy łuków	Forma graficzna	formie tabelarycznej
(AB; 7),		ALE W OD ALE 3 W 4 OD 3 4

III. Konsolidacja materiałów: studenci proszeni są o podział na grupy i wykonanie zadań. Pracując w małej grupie, uczniowie omawiają modele w oparciu o wiedzę teoretyczną zdobytą na początku lekcji. W ten sposób uzyskuje się powtarzalność i konsolidację materiału.

Zadanie 2 (slajd 13)

IV. Podsumowanie lekcji

Chłopaki, jakich nowych słów się dzisiaj nauczyliście? (Liczba, wierzchołek wykresu, krawędzie wykresu.)

Co mogą przedstawiać wierzchołki wykresu? (Miasta; obiekty, które są; połączone.)

Co oznaczają krawędzie wykresu (ścieżki, ruchy, kierunki)

Podaj przykład, gdzie w życiu możemy ich spotkać?

Jak wyświetlane są wykresy?

V. Praca domowa. (slajd 15)

Liczba wierzchołków nazywa się
kolejność wykresów.
Liczba krawędzi nazywa się
rozmiar wykresu.

Niektóre terminy-1

- Niech R=(a,b) będzie jedną z krawędzi grafu. Następnie
wierzchołki a i b są nazywane terminalami
wierzchołki krawędzi;
- Wierzchołki końcowe tej samej krawędzi
nazywane sąsiednimi;
- Dwie krawędzie są nazywane sąsiadującymi, jeśli mają
wspólny wierzchołek końcowy;
- Dwie krawędzie nazywane są wielokrotnymi, jeśli
zbiory ich wierzchołków końcowych pokrywają się;
- Krawędź nazywa się pętlą, jeśli jej końce
mecz.

Niektóre terminy-2

- stopień wierzchołka V jest oznaczony przez deg(V)
nazywa się liczbą krawędzi, bo
którego ten wierzchołek jest końcem;
- Wierzchołek nazywany jest izolowanym, jeśli
ona nie jest dla nikogo końcem
żebra;
- Wierzchołek nazywany jest liściem, jeśli
jest terminalem dla dokładnie jednego?
żebra. Dla arkusza q oczywiste jest, że deg(q)=1.

Przykład:

stopnie(C)=4
H1,…H4 - Liście

Inny przykład:

Miasta B i D są odizolowane
najfatalniejszy; Miasta G i E to liście.

Pełny wykres

Wykres nazywa się kompletnym, jeśli istnieje
dwa wierzchołki są połączone krawędzią.
Ile krawędzi ma pełny wykres
kolejność n?
Kompletny wykres rzędu n ma liczbę krawędzi
równa się Cn2=n!/(2*(n-2)!)=n*(n-1)/2

Udowodnijmy to...

Kompletny wykres z dwoma wierzchołkami
zawiera jedną krawędź - to oczywiste.
Podstaw n=2 do wzoru n*(n-1)/2
Otrzymujemy:
n*(n-1)/2=1
Wzór jest poprawny dla n=2

Założenie indukcji

Załóżmy, że formuła jest prawdziwa dla
wykres z k wierzchołków.
Udowodnijmy, że to implikuje:
ważność wzoru na wykres
z wierzchołkiem (k+1).

Dodajmy jeszcze jeden wierzchołek do pełnego wykresu z K wierzchołków.

I połącz to z pierwszym K
szczyty...

Otrzymujemy:

Liczymy ile żeberek mamy...

K*(K-1)/2 + K
=
K*(K+1)/2
Otrzymano ostatnie wyrażenie,
jeśli we wzorze n*(n-1)/2 zamiast n
zamiennik K+1.

Z założenia uczciwości
instrukcja dla n=k następuje
ważność oświadczenia w
n=k+1.
Twierdzenie zostało udowodnione.

Przykłady kompletnych wykresów

Ważne wyjaśnienie

Pary definiujące krawędzie w grafie nieskierowanym są nieuporządkowane (tj.
pary (a,b) i (b,a) nie różnią się)

Kierowany wykres

Jeśli krawędzie grafu są zbiorem
pary uporządkowane (tj. (a,b) ≠ (b,a)),
Mówi się, że wykres jest ukierunkowany.
(lub digraf)
Jak nadać orientację koncepcji?
wizualne znaczenie?
Bardzo proste - dostarczane są żeberka
strzałki (od początku do końca)!

Digraf przykład

Liczba mieszana

Wykres mieszany to potrójny (V, E, A).
V to zbiór wierzchołków;
E jest zbiorem nieskierowanych
żebra;
A to zbiór ukierunkowanych krawędzi.
Nawiasem mówiąc, skierowane krawędzie
nazywane są łukami.

Izomorfizm grafu

Niech będą dwa grafy G1 i G2
Jeśli istnieje korespondencja jeden do jednego F
między wierzchołkami grafów G1 i G2 tak, że:
- jeśli w grafie G1 występuje krawędź (a,b) to w grafie G2
jest krawędź (F(a),F(b))
- jeśli na wykresie G2 występuje krawędź (p,q) to na wykresie G1
jest krawędź (F-1(p),F-1(q))
wtedy grafy G1 i G2 nazywamy izomorficznymi, a
korespondencja F jest izomorfizmem.

Wyjaśnienie

Dla digrafów i grafów mieszanych
korespondencja F musi zachować
orientacja łuku.

Warunek konieczny dla izomorfizmu

W jakich warunkach między elementami?
dwa skończone zestawy
ustawić jeden do jednego
konformizm?
Wtedy i tylko wtedy liczba
elementy są takie same.
Niezbędny warunek izomorfizmu
wykresy to ta sama liczba
szczyty.

Czy ten warunek jest wystarczający?

Nie, ponieważ wierzchołki mogą być
połączone na różne sposoby.

Czy te wykresy są izomorficzne?

Liczba wierzchołków jest taka sama -
warunek konieczny jest spełniony...

Staramy się budować korespondencję F…

To nie jest izomorfizm: G1 ma krawędź (A, D),
a obrazy tych krawędzi w G2 nie są połączone.

Ponowna próba...

A to jest izomorfizm!

Czy te wykresy są izomorficzne?

Niestety nie…

Z teoretycznego punktu widzenia dwa
wykres izomorficzny jest taki sam
ten sam przedmiot (tylko, być może, inaczej przedstawiony...)

Ścieżki (łańcuchy):

Ścieżka (łańcuch) to sekwencja
szczyty:
a1, a2, … , an
gdzie sąsiednie wierzchołki ai i ai+1
połączone żebrami.
Długość ścieżki to liczba jej elementów
żebra

Przykłady ścieżek:

(A, D, C) i (A, B, D) to ścieżki. (A, B, C) nie jest drogą.

Pojęcie ścieżki do digrafu zachowuje
siłę, ale trzeba ją uzupełnić -
sąsiednie szczyty w
sekwencje
a1, a2, … , an
muszą być połączone łukami.

Cykle

Cykl to ścieżka, której początkowy i
koniec dopasowania wierzchołków.
Długość cyklu to liczba jego składników
żebra.
Cykl nazywamy prostym, jeśli występują w nim krawędzie
nie są powtarzane.
Cykl nazywa się elementarnym, jeśli:
proste, a wierzchołki w nim się nie powtarzają.

Elementy łączności

Wierzchołkami dowolnego grafu mogą być
podzielone na klasy tak, że dla
dowolne dwa wierzchołki tej samej klasy v1
a v2 jest ścieżka od v1 do v2
Klasy te nazywane są komponentami
łączność.
Jeśli wykres ma dokładnie jeden składnik
połączenie, wtedy wykres nazywa się
połączony.

Reprezentacja maszynowa grafów.

Macierz sąsiedztwa

- wyliczamy wierzchołki grafu G
kolejne liczby całkowite od 1 do n;
- Zbuduj kwadratową tabelę n×n i
wypełnij go zerami;
-Jeśli istnieje połączenie krawędzi
wierzchołki i i j, następnie w pozycjach (i,j) i (j,i)
umieścić jednostki;
- Wynikowa tabela nazywa się
macierz sąsiedztwa grafu G.

Przykład

Niektóre oczywiste właściwości macierzy sąsiedztwa

- Jeśli wierzchołek jest izolowany, to jego rząd i
kolumna będzie całkowicie pusta;
- Liczba jednostek w rzędzie (kolumna)
równy stopniowi odpowiedniego
najfatalniejszy;
- Dla grafu nieskierowanego macierz
sąsiedztwo jest symetryczne około
główna przekątna;
- Pętla odpowiada jednostce stojącej
główna przekątna.

Uogólnienie na digraf

Macierz sąsiedztwa dla digrafu
można zbudować podobnie
sposób, ale weź pod uwagę kolejność
wierzchołki, możesz to zrobić:
Jeśli łuk pochodzi z wierzchołka j i
wprowadza wierzchołek k, a następnie w pozycji (j,k)
ustaw macierze sąsiedztwa na 1, a in
pozycja (k, j) zestaw -1.

Macierz incydentów

- wyliczamy wierzchołki grafu G
kolejne liczby całkowite od 1 do
n;
- Zbuduj prostokątny stół z
n wierszy i m kolumn (kolumn
odpowiadają krawędziom wykresu);
- Jeśli j-ta krawędź ma zacisk
wierzchołek k, a następnie na pozycji
(k,j) jest ustawione na jeden. We wszystkim
w innych przypadkach jest ustawiony na zero.

Macierz incydentów dla digrafu

- Jeśli j-ty łuk pochodzi z wierzchołka k,
wtedy pozycja (k,j) jest ustawiona na 1;
- Jeśli j-ty łuk wchodzi w wierzchołek k, to
w pozycji (k,j) umieść -1.
- W pozostałych przypadkach w pozycji (k, j)
pozostaje zero.

Ponieważ kolumny macierzy
wypadki opisują krawędzie, więc
każda kolumna może nie zawierać
więcej niż dwa niezerowe elementy

Przykład macierzy zapadalności

Lista żeber

Inny sposób reprezentowania wykresu
– tablica dwuwymiarowa (lista par).
Liczba par jest równa liczbie krawędzi
(lub łuki).

Przykład listy krawędzi

Porównanie różnych metod prezentacji

- Lista krawędzi jest najbardziej zwarta i
macierz najmniejszego występowania
kompaktowy;
- Matryca zapadalności jest przydatna, gdy
szukaj cykli;
- Łatwiejsza macierz sąsiedztwa
reszta jest w użyciu.

Przechodzenie przez wykres

Przechodzenie przez graf jest jego wyliczeniem.
wierzchołki takie, że każdy wierzchołek
oglądane raz.

Umowa-1

Przed przystąpieniem do wyszukiwania wykresu
z n wierzchołków utwórz tablicę Chk
n elementów i wypełnij go
zera.
Jeśli Chk[i] = 0, to i-ty wierzchołek już
nie oglądane.

Umowa-2

Uzyskajmy strukturę danych
(repozytorium), w którym będziemy
zapamiętać wierzchołki w procesie
objazd. Interfejs do przechowywania
powinien pełnić trzy funkcje:
- Przynieś górę;
- Wyciąg z góry;
- Sprawdź, czy magazyn jest pusty;

Zgoda-3

Gdy wierzchołek j jest umieszczony w
repozytorium, jest oznaczone jako
oglądane (tj. zainstalowane
Chk[j]=1)

Algorytm obejścia-1

1) Bierzemy dowolny wierzchołek początkowy,
wydrukuj go i odłóż do magazynu;

3) Wyjmij wierzchołek Z z magazynu;
4) Jeśli istnieje wierzchołek Q powiązany z Z, a nie
sprawdzone, następnie zwracamy Z do magazynu,
przechowuj Q, drukuj Q;
5) Przejdź do kroku 2

Algorytm obejścia-2

1) Bierzemy dowolny wierzchołek początkowy i
umieszczamy go w magazynie;
2) Czy magazyn jest pusty? Jeśli TAK - koniec;
3) Wyjmij wierzchołek Z z magazynu, wydrukuj i
usunąć z magazynu;
4) Przechowujemy wszystkie wierzchołki,
związane z Z i jeszcze nieoznaczone;
5) Przejdź do kroku 2

Jakie struktury danych nadają się do przechowywania?

- Stack (PUSH - przynieś; POP - usuń)
- Kolejka (ENQUE - enter; DEQUE -
wyciąg)
Obie struktury umożliwiają sprawdzanie
dostępność danych.

Algorytm-1 w połączeniu ze stosem
nazywa się przechodzeniem w głąb
Algorytm-2 połączony z kolejką
nazywa się najpierw wszerz

Graf jest skończonym zbiorem wierzchołków V i zbiorem krawędzi R łączących pary wierzchołków, G=(V,R). Siły zbiorów V i R są równe N i M. Zbiór krawędzi może być pusty. Przykładami wierzchołków są obiekty o dowolnym charakterze (osady, sieci komputerowe). Przykładami krawędzi są drogi, boki, linie.

Wierzchołki połączone krawędzią nazywane są sąsiednimi. Krawędzie, które mają wspólny wierzchołek, są również nazywane sąsiednimi. Krawędź i dowolny z jej dwóch wierzchołków nazywamy incydentem. Stopień wierzchołka to liczba przychodzących do niego krawędzi. Każdy wykres może być reprezentowany na płaszczyźnie przez zbiór punktów odpowiadających wierzchołkom, które są połączone liniami odpowiadającymi krawędziom.

Ścieżka wykresu to sekwencja wierzchołków i krawędzi. Trasa jest zamknięta (cykliczna), jeśli wierzchołki początkowe i końcowe są takie same. Trasa jest prostą ścieżką, jeśli wszystkie wierzchołki i krawędzie są różne. Wykres jest połączony, jeśli każdy wierzchołek jest osiągalny z dowolnego innego. Wierzchołki, które nie mają krawędzi incydentów, nazywane są izolowanymi.

Macierz incydentów

Listy komunikacyjne

Lista żeber

Macierz sąsiedztwa połączonego ważonego grafu nieskierowanego grafu

Budowa połączonego drzewa opinającego o minimalnej wadze. Algorytm Kruskala Z grafu usuwane są wszystkie krawędzie i otrzymuje się podgraf rozpinający, w którym wszystkie wierzchołki są izolowane. Każdy wierzchołek jest umieszczony w podzbiorze singletona. Krawędzie są sortowane rosnąco według wag. Krawędzie są kolejno, w porządku rosnącym ich wag, włączane do drzewa opinającego.

Istnieją 4 przypadki: 1) oba wierzchołki dołączonej krawędzi należą do podzbiorów jednoelementowych, a następnie są łączone w nowy, połączony podzbiór; 2) jeden z wierzchołków należy do podzbioru połączonego, a drugi nie, to drugi należy do podzbioru, do którego należy pierwszy; 3) oba wierzchołki należą do różnych połączonych podzbiorów, następnie łączymy podzbiory; 4) Oba wierzchołki należą do tego samego połączonego podzbioru, wtedy wykluczamy tę krawędź.

Przykład budowania drzewa opinającego o minimalnej wadze dla grafu GG Wykonane akcje Zbiór wierzchołków Wykres 1 Zbuduj podgraf opinający z izolowanymi i wierzchołkami Otrzymujemy 5 podzbiorów pojedynczych: (V 1 ), (V 2 ), (V 3 ), ( V 4 ), (V 5 ) 2Znajdź krawędź minimalnej wagi (R 15) i dodaj ją do podgrafu opinającego Utwórz spójny podzbiór wierzchołków: (V 1,V 5 ). Zapisz podzbiory (V 2 ), (V 3 ), (V 4 )

Wykonywane akcje Zbiór wierzchołkówWykres 3Wśród pozostałych odszukaj krawędź minimalnej masy (R 45) i dodaj ją do podwykresu spinającego Dodaj wierzchołek do połączonego podzbioru: (V 1,V 5, V 4 ). Zapisujemy podzbiory (V 2 ), (V 3 ) 4Wśród pozostałych odnajdujemy krawędź minimalnej masy (R 23) i dodajemy ją do podwykresu spinającego Utworzyć nowy połączony podzbiór wierzchołków: (V 2,V 3 ) . Zachowujemy pierwszy połączony podzbiór (V 1,V 5, V 4 ).

Wykonywane akcje Zbiór wierzchołkówWykres 5Wśród pozostałych znajdź krawędź minimalnej masy (R 25) i dodaj ją do podwykresu spinającego Połącz podzbiory w jeden połączony podzbiór (V 1,V 5, V 4,V 2,V 3 ). 6Pozostałe krawędzie nie są uwzględnione na wykresie, ponieważ wszystkie ich wierzchołki należą już do tego samego połączonego zestawu.

Wykonywane akcje Zbiór wierzchołków Otrzymano graf 7A, który: jest grafem opinającym (uwzględnione są wszystkie wierzchołki); połączone (wszystkie wierzchołki mogą być połączone trasami); drzewo (bez cykli); ma minimalną wagę. 8 Otrzymane drzewo opinające ma minimalną wagę: R 12 +R 25 +R 15 +R 45 = =80 9 Liczba cykliczna wykresu G wynosi γ=m-n+1=8-5+1=4, co odpowiada liczba krawędzi nie w drzewo.

Deklarowanie zmiennych Dwie pięcioelementowe tablice liczb całkowitych X i Y do przechowywania współrzędnych wierzchołków grafu Dwuwymiarowa tablica R do przechowywania wag krawędzi grafu Zmienne całkowite i, n i k do liczników cykli Zmienna całkowita S do przechowywania sumy wag krawędzi drzewa o minimalnej wadze

Generowanie losowych współrzędnych 5 wierzchołków grafu (pętla nad i). Obliczanie wag krawędzi. Wyprowadzenie macierzy sąsiedztwa ważonego digrafu (zagnieżdżone pętle w n i in k) Wyprowadzenie macierzy sąsiedztwa ważonego grafu nieskierowanego – połowa elementów macierzy początkowej (wartość początkowa k=n+1) Treść programu