Nieformalnie wykres można traktować jako zbiór punktów i linii łączących te punkty, ze strzałkami lub bez.
Za pierwsze dzieło teorii grafów jako dyscypliny matematycznej uważa się pracę Eulera (1736), w której rozważano problem mostów królewieckich. Euler pokazał, że nie da się ominąć siedmiu mostów miejskich i wrócić do punktu wyjścia, przechodząc przez każdy most dokładnie raz. Teoria grafów nabrała kolejnego rozmachu prawie 100 lat później wraz z rozwojem badań w dziedzinie sieci elektrycznych, krystalografii, chemii organicznej i innych nauk.
Nawet nie zauważając tego, cały czas spotykamy się z wykresami. Na przykład wykresem jest diagram linii metra. Kropki na nim reprezentują stacje, a linie przedstawiają trasy pociągów. Badając nasze pochodzenie i śledząc je aż do odległego przodka, budujemy tak zwane drzewo genealogiczne. A to drzewo jest wykresem.
Wykresy służą jako wygodny sposób opisywania relacji między obiektami. Wcześniej używaliśmy wykresów jako sposobu wizualnego przedstawienia skończonych relacji binarnych.
Ale wykres służy nie tylko jako ilustracja. Przykładowo, biorąc pod uwagę wykres przedstawiający sieć dróg pomiędzy zaludnionymi obszarami, można wyznaczyć trasę z punktu A do punktu B. Jeśli takich tras jest kilka, to chciałbyś wybrać tę optymalną w pewnym sensie, np. najkrótszy lub najbezpieczniejszy. Aby rozwiązać problem selekcji, należy przeprowadzić pewne obliczenia na wykresach. Przy rozwiązywaniu takich problemów wygodnie jest stosować techniki algebraiczne, a samo pojęcie wykresu wymaga sformalizowania.
Metody teorii grafów są szeroko stosowane w matematyce dyskretnej. Nie da się bez nich obejść przy analizie i syntezie różnych dyskretnych konwerterów: bloków funkcjonalnych komputerów, pakietów oprogramowania itp.
Obecnie teoria grafów obejmuje wiele materiału i aktywnie się rozwija. Prezentując ją, ograniczymy się tylko do części wyników, główny nacisk położymy na opis i uzasadnienie niektórych szeroko rozpowszechnionych algorytmów analizy grafów stosowanych w teorii języków formalnych.
Podstawowe definicje
Wykresy, jak już wspomniano w przykładach, są sposobem „wizualizacji” powiązań pomiędzy określonymi obiektami. Połączenia te mogą być „ukierunkowane”, jak na przykład w drzewie genealogicznym, lub „nieskierowane” (sieć dwukierunkowych drogi). Zgodnie z tym w teorii grafów wyróżnia się dwa główne typy grafów: skierowane (lub skierowane) i nieskierowane.
Metody prezentacji
Dotychczas zdefiniowaliśmy grafy skierowane i nieskierowane, przedstawiając je za pomocą rysunków. Można zdefiniować wykres jako parę zbiorów, zgodnie z definicją, ale ta metoda jest dość uciążliwa i ma raczej znaczenie teoretyczne. Rozwój algorytmicznych podejść do analizy właściwości grafów wymaga innych sposobów opisywania wykresów, które są bardziej odpowiednie do praktycznych obliczeń, w tym z wykorzystaniem komputera. Przyjrzyjmy się trzem najczęstszym sposobom przedstawiania wykresów.
Drzewa
Definicja 5.5. Drzewo nieskierowane to spójny i acykliczny graf nieskierowany. Definicja 5.6. Drzewo skierowane to graf skierowany bez konturu, w którym półstopień dowolnego wierzchołka jest nie większy niż 1 i istnieje dokładnie jeden wierzchołek, zwany pierwiastkiem drzewa skierowanego, którego półstopień wynosi 0.
Drzewo opinające o najmniejszej wadze
Następujący problem jest znany w teorii grafów jako problem Steinera: n punktów jest podanych na płaszczyźnie; należy je połączyć odcinkami prostymi w taki sposób, aby łączna długość odcinków była minimalna.
Metody systematycznego przechodzenia przez wierzchołki grafu
Ważnymi problemami teorii grafów są problemy globalnej analizy zarówno grafów nieskierowanych, jak i skierowanych. Zadania te obejmują na przykład zadanie znalezienia cykli lub konturów, obliczenie długości ścieżek pomiędzy parami wierzchołków, wypisanie ścieżek o określonych właściwościach itp. Analizę grafów globalnych należy odróżnić od analizy lokalnej, której przykładem jest problem wyznaczania zbiorów poprzedników i następników ustalonego wierzchołka grafu skierowanego.
Problem ścieżki w grafach ważonych skierowanych
Izomorfizm wykresu
Dla grafu skierowanego (V, E) zbiór E łuków można uznać za wykres binarnej relacji bezpośredniej osiągalności określonej na zbiorze wierzchołków. W grafie nieskierowanym (V, E) zbiór E krawędzi jest zbiorem par nieuporządkowanych. Dla każdej pary nieuporządkowanej (u, v) ∈ E możemy założyć, że wierzchołki u i v są połączone symetryczną relacją binarną p, tj. (u, v) ∈ р i (v, u) ∈ р.
Sortowanie topologiczne
Definicja 5.17. Sieć skierowana (lub po prostu sieć) to bezkonturowy graf skierowany*. Ponieważ sieć jest grafem bezkonturowym, można wykazać, że istnieją wierzchołki (węzły) sieci o zerowym stopniu zewnętrznym, a także wierzchołki (węzły) o zerowym stopniu wejściowym. Te pierwsze nazywane są ujściami lub wyjściami sieci, a te drugie źródłami lub wejściami sieci.
Elementy cyklomatyki
Omawiając algorytm przeszukiwania w głąb w grafie nieskierowanym, podjęto kwestię poszukiwania tzw. cykli podstawowych grafu. W tym przypadku przez cykl podstawowy rozumiano cykl zawierający dokładnie jedną odwrotną krawędź i ustalono zgodność jeden do jednego między cyklami podstawowymi i odwrotnymi krawędziami; cykle podstawowe powstają wtedy, gdy dowolny podział wszystkich krawędzi grafu nieskierowanego na drzewa (tworzące las maksymalnych krawędzi oryginalnego wykresu) i odwrotnie, a w ogólnym przypadku ten podział można określić całkowicie niezależnie od algorytmu przeszukiwania w głąb. Przeszukiwanie w głąb to tylko jeden ze sposobów wdrożenia takiej partycji.
Teoria grafów to dział matematyki stosowany w informatyce i programowaniu, ekonomii, logistyce i chemii.
Co to jest wykres
Diagramy graficzne są często używane do opisu struktury systemów. Elementy w nich są reprezentowane przez okręgi, kropki, kwadraty itp., a połączenia między elementami są reprezentowane przez linie lub strzałki. W tym przypadku nie ma znaczenia ani sposób przedstawienia elementów, ani długość czy kształt linii – liczy się tylko to, jakie elementy są ze sobą połączone. Zatem graf jest parą postaci (A, M), gdzie A jest skończonym zbiorem wierzchołków, a M jest zbiorem krawędzi - linii łączących niektóre wierzchołki.
Podstawowe pojęcia teorii grafów
Zorientowany wykres lub dwuznak (patrz rysunek poniżej) ma zorientowane krawędzie, zwane łukami i oznaczone strzałkami. Łuk można oznaczyć przez uporządkowaną parę wierzchołków, które łączy, początek i koniec.
Wykres nieskierowany (patrz rysunek poniżej) ma krawędzie narysowane jako linie bez orientacji. W związku z tym para wierzchołków połączonych krawędzią jest nieuporządkowana. Obydwa wierzchołki są końcami krawędzi.
Jeśli wierzchołki a i b są końcami krawędzi (lub początkiem i końcem łuku) grafu, to mówimy, że wierzchołki a i b są incydentne z tą krawędzią (łukiem), a krawędź (łuk) jest również incydent z wierzchołkami a i b. Jeśli wierzchołki a i b są końcami krawędzi, wówczas wierzchołki (a i b) nazywane są sąsiadującymi.
Najczęściej rozważamy grafy, których krawędzie są jednego rodzaju – niezależnie od tego, czy są skierowane, czy nie.
Jeśli krawędzie mają ten sam początek i koniec, wówczas nazywa się je krawędziami wielokrotnymi, a graf, w którym występują, nazywa się multigrafem.
Teoria grafów wykorzystuje również koncepcję „pętli” – krawędzi, która wychodzi i przechodzi do tego samego wierzchołka. Wykres zawierający pętle nazywa się pseudografem.
Najpopularniejsze są grafy nieskierowane, które nie mają wielu krawędzi ani pętli. Takie wykresy nazywane są zwykłymi. Nie mają wielu krawędzi, więc możemy zidentyfikować krawędź i odpowiadającą jej parę wierzchołków.
Każdy wierzchołek dwuznaku charakteryzuje się:
- Pół stopnia wyniku. Jest to liczba wychodzących z niego łuków.
- Pół stopnia podejścia. Jest to liczba łuków wchodzących do danego wierzchołka.
Suma półstopni wejścia dwuznaku, a także suma półstopni wyniku, są równe całkowitej liczbie łuków wykresu.
W grafie nieskierowanym każdy wierzchołek charakteryzuje się stopniem wierzchołka. Jest to liczba krawędzi przypadających na wierzchołek. Całkowita suma stopni wierzchołków grafu to liczba krawędzi pomnożona przez dwa: każda krawędź wniesie wkład równy dwa.
Wierzchołek o stopniu 0 nazywany jest izolowanym.
Wierzchołek wiszący to wierzchołek o stopniu 1.
Teoria grafów nazywa pustym grafem, w którym nie ma krawędzi. Graf pełny to zwykły graf, w którym dowolne 2 wierzchołki sąsiadują ze sobą.
Wykresy ważone to wykresy, których wierzchołkom lub krawędziom (łukom) lub obu wierzchołkom i krawędziom (łukom) przypisano określone liczby. Nazywa się je skalami. Drugi rysunek przedstawia graf nieskierowany, którego krawędzie są ważone.
Wykresy: izomorfizm
Pojęcie izomorfizmu jest używane w matematyce. W szczególności teoria grafów definiuje to w następujący sposób: dwa grafy U i V są izomorficzne, jeśli na tych grafach zachodzi bijekcja pomiędzy zbiorami ich wierzchołków: każde 2 wierzchołki grafu U są połączone krawędzią wtedy i tylko wtedy, gdy w graf V te same wierzchołki są połączone krawędzią (które mogą mieć różne nazwy). Poniższy rysunek przedstawia dwa grafy izomorficzne, na których opisana powyżej bijekcja istnieje pomiędzy wierzchołkami pokolorowanymi tymi samymi kolorami zarówno na pierwszym, jak i drugim grafie.
Ścieżki i cykle
Ścieżka w grafie nieskierowanym lub skierowanym to sekwencja krawędzi, gdzie każda następna zaczyna się w wierzchołku, w którym kończy się poprzednia. Prosta ścieżka to taka, w której wszystkie wierzchołki, z wyjątkiem początku i końca, oraz krawędzie są różne. Cykl w dwugrafie to ścieżka, której wierzchołki początkowy i końcowy pokrywają się i która zawiera co najmniej jedną krawędź. Cykl w grafie nieskierowanym to ścieżka zawierająca co najmniej trzy różne krawędzie. Na drugim rysunku cyklem jest na przykład ścieżka (3, 1), (6, 3), (1, 6).
Teoria grafów w programowaniu służy do konstruowania diagramów grafowych algorytmów.
Książka K. Berge jest pierwszą w języku rosyjskim książką dotyczącą teorii grafów. Tymczasem w ostatnich latach gwałtownie wzrosło zainteresowanie teorią zarówno ze strony matematyków, jak i przedstawicieli szerokiej gamy dyscyplin. Wyjaśnia to fakt, że metody teorii grafów z powodzeniem rozwiązują wiele problemów z zakresu teorii obwodów elektrycznych, teorii łańcuchów transportowych, teorii informacji, cybernetyki itp.
W książce Berge'a teoria grafów przedstawiona jest sekwencyjnie, zaczynając od samych podstaw. Zakłada się, że czytelnik ma bardzo skromną wiedzę matematyczną, choć posiada pewną kulturę matematyczną. W tekście pojawiają się liczne, często zabawne, przykłady. Książkę można wykorzystać do wstępnego studiowania teorii grafów. Zawodowi matematycy również znajdą w niej wiele ciekawych rzeczy.
Algorytm bezpośredniej identyfikacji cyklu Eulera.
[Fleury]. Rozważmy multigraf G spójny, którego wszystkie wierzchołki mają stopień parzysty, i spróbujemy go narysować jednym pociągnięciem, bez konieczności poprawiania już narysowanego fragmentu trajektorii w procesie konstrukcji. Wystarczy przestrzegać następującej zasady:
1 Wychodzimy z dowolnego wierzchołka a; Przekreślamy każdą mijaną krawędź.
2 Nigdy nie idziemy wzdłuż takiej krawędzi, która w rozpatrywanej chwili jest przesmykiem (czyli po usunięciu graf utworzony przez nieskrzyżowane krawędzie dzieli się na dwie połączone składowe, posiadające co najmniej jedną krawędź każda),
Stosując się do tej zasady będziemy zawsze w korzystnej sytuacji, gdyż gdy będziemy w punkcie x = a, graf (o nieskrzyżowanych krawędziach) ma dwa wierzchołki stopnia nieparzystego: x i a; jeśli odrzucimy izolowane wierzchołki, pozostanie spójny graf, który na mocy Twierdzenia 1 ma łańcuch Eulera zaczynający się od x.
Treść
Wstęp
Rozdział 1. Podstawowe definicje
Zbiory i odwzorowania wielowartościowe
Wykres. Ścieżki i kontury
Obwody i cykle
Rozdział 2. Wstępne badania quasi-porządku
Quasi-porządek określony przez graf
Wykres indukcyjny i podstawy
Rozdział 3. Funkcja porządkowa i funkcja
Grundy'ego dla nieskończonego wykresu
Ogólne rozważania dotyczące grafów nieskończonych
Funkcja porządkowa
Funkcje Grundy’ego
Operacje na grafach
Rozdział 4. Podstawowe liczby teorii grafów
Liczba cyklomatyczna
Liczba chromatyczna
Numer stabilności wewnętrznej
Numer stabilności zewnętrznej
Rozdział 5. Jądra wykresów
Twierdzenia o istnieniu i jedyności
Zastosowanie do funkcji Grundy'ego
Rozdział 6. Gry graficzne
Gra Nim
Ogólna definicja gry (z pełnymi informacjami)
Strategie
Rozdział 7. Problem najkrótszej ścieżki
Procesy etapowe Niektóre uogólnienia
Rozdział 8. Sieci transportowe
Problem z maksymalnym przepływem Problem z najmniejszym przepływem
Problem przepływu zgodnego z wartością zadaną
Niekończące się sieci transportowe
Rozdział 9. Twierdzenie o połówkach potęg
Półstopień wyjścia i wejścia
Rozdział 10. Dopasowywanie prostego wykresu
Maksymalny problem dopasowania
Prosty brak wykresu
Algorytm węgierski
Uogólnienie na przypadek nieskończony
Zastosowanie do teorii macierzy
Rozdział 11. Czynniki
Ścieżki Hamiltona i kontury Hamiltona
Znalezienie czynnika
Znalezienie wykresu częściowego z podanymi półstopniami
Rozdział 12. Centra wykresów
Centra
Promień
Rozdział 13. Średnica grafu silnie spójnego
Ogólne właściwości grafów silnie połączonych bez pętli
Średnica
Rozdział 14. Macierz sąsiedztwa grafów
Zastosowanie konwencjonalnych operacji macierzowych
Problemy z liczeniem
Problem lidera
Korzystanie z operacji boolowskich
Rozdział 15. Macierze incydentów
Całkowicie unimodularne macierze
Całkowicie unimodularne systemy
Macierze cyklomatyczne
Rozdział 16. Drzewa i drzewa przodków
Drzewa
Badania analityczne
Wielkie drzewa
Rozdział 17. Problem Eulera
Cykle Eulera Kontury Eulera
Rozdział 18. Dopasowywanie dowolnego wykresu
Teoria obwodów przemiennych
Znajdowanie grafu cząstkowego o zadanych stopniach wierzchołków
Idealne dopasowanie
Zastosowanie do wewnętrznego numeru stabilności
Rozdział 19. Faktoidy
Cykle Hamiltona i faktoidy
Warunek konieczny i wystarczający istnienia faktoroidu
Rozdział 20. Łączność grafów
Punkty artykulacyjne
Wykresy bez przegubów
h-spójne wykresy
Rozdział 21. Wykresy planarne
Podstawowe właściwości
Uogólnienie
Wzbogacenie
I. Poza ogólną teorią, grami
II. O zadaniach transportowych
III. O wykorzystaniu potencjalnych koncepcji w sieciach transportowych
IV. Nierozwiązane problemy i niepotwierdzone założenia
V. O niektórych podstawowych zasadach liczenia (J. Riguet)
VI. Dodatki do tłumaczenia rosyjskiego (A.A. Zykov i G.I. Kozhukhin)
Literatura
Teoria grafów i książka C. Berge (posłowie do tłumaczenia rosyjskiego)
Indeks znaków
Indeks nazw
Indeks tematyczny.
Pobierz e-book za darmo w wygodnym formacie, obejrzyj i przeczytaj:
Pobierz książkę Teoria grafów i jej zastosowania, Berge K. – fileskachat.com, do szybkiego i bezpłatnego pobrania.
Teoria grafów to dziedzina matematyki dyskretnej, która bada obiekty reprezentowane jako pojedyncze elementy (wierzchołki) i połączenia między nimi (łuki, krawędzie).
Teoria grafów wywodzi się z rozwiązania problemu mostów królewieckich w 1736 roku przez słynnego matematyka Leonarda Eulera(1707-1783: urodził się w Szwajcarii, mieszkał i pracował w Rosji).
Problem z mostami w Królewcu.
W pruskim mieście Królewcu nad rzeką Pregal znajduje się siedem mostów. Czy można znaleźć trasę pieszą, która przecina każdy most dokładnie raz i zaczyna się i kończy w tym samym miejscu?
Graf, w którym istnieje trasa rozpoczynająca się i kończąca w tym samym wierzchołku i przechodząca wzdłuż wszystkich krawędzi grafu dokładnie raz, nazywa sięWykres Eulera.
Nazywa się sekwencję wierzchołków (może się powtarzać), przez którą przechodzi pożądana trasa, a także sama trasaCykl Eulera .
Problem trzech domów i trzech studni.
Są tam trzy domy i trzy studnie, jakoś umiejscowione na płaszczyźnie. Narysuj ścieżkę z każdego domu do każdej studni, tak aby ścieżki się nie przecinały. Problem ten został rozwiązany (wykazano, że nie ma rozwiązania) przez Kuratowskiego (1896–1979) w 1930 r.
Problem czterech kolorów. Podział płaszczyzny na nieprzecinające się obszary nazywa się kartą. Obszary mapy nazywane są sąsiadującymi, jeśli mają wspólną granicę. Zadanie polega na pokolorowaniu mapy w taki sposób, aby żadne dwa sąsiednie obszary nie były pomalowane tym samym kolorem. Od końca XIX wieku znana jest hipoteza, że wystarczą do tego cztery kolory. Hipoteza nie została jeszcze udowodniona.
Istotą opublikowanego rozwiązania jest wypróbowanie dużej, ale skończonej liczby (około 2000) typów potencjalnych kontrprzykładów do twierdzenia o czterech kolorach i wykazanie, że ani jeden przypadek nie jest kontrprzykładem. Poszukiwania te program zakończył po około tysiącu godzin pracy superkomputera.
Nie da się sprawdzić powstałego rozwiązania „ręcznie” – zakres wyliczeń przekracza możliwości człowieka. Wielu matematyków zadaje sobie pytanie: czy taki „dowód programowy” można uznać za ważny dowód? Przecież w programie mogą być błędy...
Możemy zatem polegać jedynie na umiejętnościach programistycznych autorów i wierzyć, że zrobili wszystko dobrze.
Definicja 7.1. Liczyć G= G(V, mi) jest zbiorem dwóch zbiorów skończonych: V – tzw wiele wierzchołków oraz zbiór E par elementów z V, tj. EÍV'V, tzw wiele krawędzi, jeśli pary są nieuporządkowane, lub wiele łuków, jeśli pary są zamówione.
W pierwszym przypadku wykres G(V, mi) zwany niezorientowany, w sekundę - zorientowany.
PRZYKŁAD. Graf mający zbiór wierzchołków V = (a,b,c) i zbiór krawędzi E =((a, b), (b, c))
PRZYKŁAD. Wykres z V = (a, b, c, d, e) i E = ((a, b), (a, e), (b, e), (b, d), (b, c) , (płyta CD)),
Jeśli e=(v 1 ,v 2), еОЕ, to mówią, że krawędzią jest e łączy wierzchołki v 1 i v 2.
Nazywa się dwa wierzchołki v 1, v 2 przylegający, jeśli łączy je krawędź. W tej sytuacji wywoływany jest każdy z wierzchołków incydent odpowiednia krawędź .
Dwa różne żebra przylegający, jeśli mają wspólny wierzchołek. W tej sytuacji wywoływana jest każda z krawędzi przypadkowy odpowiedni wierzchołek .
Liczba wierzchołków grafu G oznaczmy w, a liczba krawędzi wynosi mi:
.
Geometryczna reprezentacja wykresów jest następująca:
1) wierzchołkiem wykresu jest punkt w przestrzeni (na płaszczyźnie);
2) krawędź grafu nieskierowanego – odcinek;
3) łuk grafu skierowanego – segment skierowany.
Definicja 7.2. Jeżeli w krawędzi e=(v 1 ,v 2) v 1 =v 2 to krawędź e nazywa się pętla. Jeśli graf pozwala na pętle, wówczas nazywa się go wykres z pętlami Lub pseudograf .
Jeżeli graf pozwala na więcej niż jedną krawędź pomiędzy dwoma wierzchołkami, wówczas nazywa się to grafem multigraf .
Jeśli każdy wierzchołek grafu i/lub krawędzi jest oznaczony etykietą, wówczas taki graf nazywa się wyraźny (Lub załadowany ). Jako znaki zwykle używane są litery lub liczby całkowite.
Definicja 7.3. Wykres G (V , mi ) zwany podpunkt (Lub część ) wykres G(V,mi), Jeśli V V, mi mi. Jeśli V = V, To G zwany podgraf rozpinający G.
Przykład 7 . 1 . Biorąc pod uwagę graf nieskierowany.
Definicja 7.4. Wykres nazywa się kompletny , Jeśli każdy jego dwa wierzchołki są połączone krawędzią. Kompletny wykres z N wierzchołki są oznaczone K N .
Liczy K 2 , DO 3, DO 4 i K 5 .
Definicja 7.5. Wykres G=G(V, mi) jest nazywany dwuliścienny , Jeśli V można przedstawić jako sumę zbiorów rozłącznych, powiedzmy V=AB, więc każda krawędź ma postać ( w I , w J), Gdzie w I A I w J B.
Każda krawędź łączy wierzchołek A z wierzchołkiem B, ale żadne dwa wierzchołki z A ani dwa wierzchołki z B nie są połączone.
Graf dwudzielny nazywa się kompletny dwuliścienny liczyć K M , N, Jeśli A zawiera M szczyty, B zawiera N wierzchołków i dla każdego w I A, w J B mamy ( w I , w J)mi.
Tym samym dla każdego w I A, I w J Błączy je krawędź.
K. 12 K. 23 K. 22 K. 33
Przykład 7 . 2 . Skonstruuj kompletny graf dwudzielny K 2.4 i pełny wykres K 4 .
Wykres jednostkowyN-wymiarowa kostkaW N .
Wierzchołki grafu są n-wymiarowymi zbiorami binarnymi. Krawędzie łączą wierzchołki różniące się jedną współrzędną.
Przykład: 
Wykresy to zabawny, satysfakcjonujący i przerażający temat. Teoria grafów - „Horror studenta”. Algorytmy graficzne to niesamowite umysły ludzi, którzy je odkryli.
Co to jest wykres? Aby odpowiedzieć na to pytanie moim czytelnikom, opiszę temat nieco inaczej.
Wykres to zbiór obiektów.
W większości problemów są to obiekty tego samego typu. (Wiele miast, wiele domów, wiele osób lub wiele innych rzeczy tego samego typu)
Aby rozwiązać problemy z takim zbiorem, należy każdy obiekt z tego zbioru oznaczyć jako coś. Powszechnie przyjmuje się, że właśnie to zjawisko nazywa się wierzchołkami grafu.
Wygodnie jest opisywać wykresy i podstawowe definicje obrazami, dlatego aby przeczytać tę stronę, należy dołączyć obrazy.
Jak pisałem wcześniej, graf to zbiór obiektów. Obiekty te są zazwyczaj tego samego typu. Najłatwiej podać przykład w miastach. Każdy z nas wie, czym jest miasto i czym jest droga. Każdy z nas wie, że do miasta mogą być drogi lub nie. Ogólnie rzecz biorąc, dowolny zbiór obiektów można scharakteryzować jako graf.
Jeśli mówimy o grafie jak o miastach, to między miastami można budować drogi, albo można je gdzieś zniszczyć, a nie zbudować, lub miasto jest na ogół położone na wyspie, nie ma mostu, a interesujące są tylko drogi utwardzone . Pomimo tego, że do takiego miasta nie prowadzi droga, to miasto to można uwzględnić w wielu analizowanych obiektach, a wszystkie obiekty razem wzięte tworzą zbiór obiektów, czyli najprościej – graf.
Z pewnością czytałeś podręczniki i widziałeś taki zapis G(V,E) lub coś podobnego. Zatem V jest jakimś pojedynczym obiektem z całego zbioru obiektów. W naszym przypadku zbiorem obiektów są miasta, zatem V jest konkretnym miastem. Ponieważ obiektami niekoniecznie są miasta, a słowo obiekt może być mylące, taki obiekt ze zbioru można nazwać punktem, punktem lub czymś innym, ale najczęściej nazywa się go wierzchołkiem wykresu i jest oznaczony literą V.
W programowaniu jest to zwykle kolumna lub wiersz dwuwymiarowej tablicy, gdzie tablica nazywana jest macierzą sąsiedztwa lub macierzą występowania.
W literaturze, Internecie i ogólnie wszędzie tam, gdzie pisze się coś o grafach, można spotkać się z pojęciami takimi jak łuki i krawędzie. Ten rysunek pokazuje krawędzie wykresu. Te. są to trzy krawędzie E1, E2 i E3.
Łuk i krawędź różnią się tym, że krawędź jest połączeniem dwukierunkowym. Chciał, poszedł do sąsiada, chciał, wrócił od sąsiada. Jeśli nie jest to zbyt jasne, możesz wyobrazić sobie dom, lotnisko, latający samolot i spadochroniarza. Spadochroniarz może polecieć ze swojego domu na lotnisko, ale kiedy dotrze na lotnisko, przypomina sobie, że zapomniał w domu swojego szczęśliwego spadochronu, po czym wraca do domu i bierze spadochron. — Droga, po której można chodzić tam i z powrotem, nazywa się krawędzią.
Jeśli skoczek jest w samolocie i wyskakuje z samolotu, ale zapomniał założyć w samolocie swój szczęśliwy spadochron, czy skoczek będzie w stanie podnieść to, o czym zapomniał? Ścieżkę biegnącą tylko w jednym kierunku nazywamy łukiem. Zwykle mówimy, że krawędź łączy dwa wierzchołki, a łuk przechodzi od jednego wierzchołka do drugiego.
Na tym rysunku wykres zawiera tylko łuki. Łuki na wykresie są oznaczone strzałkami, ponieważ dostępny kierunek jest tak wyraźny. Jeśli graf składa się tylko z takich łuków, wówczas taki graf nazywa się skierowanym.
 |
Często spotykasz się z pojęciami przylegania i występowania. Na rysunku dwie krawędzie prowadzące do jednego punktu zaznaczono na czerwono. Takie krawędzie, podobnie jak opisane powyżej wierzchołki, nazywane są także sąsiadującymi. |
Wiele nie jest opisanych, ale ta informacja może komuś pomóc.