Wykresy informatyki: definicja, typy, zastosowania, przykłady. Teoria wykresów w informatyce

Wykresy informatyki są sposobem definiowania związków w kombinacji elementów. Są to główne cele badania teorii grafów.

Podstawowe definicje

Jaki jest wykres w informatyce? Zawiera zestaw obiektów zwanych wierzchołkami lub węzłami, których kilka par związanych jest z tak zwanymi. Żebra. Na przykład wykres na rysunku (a) składa się z czterech węzłów, oznaczonych A, B, C i D, z których B jest połączony z każdym z pozostałych trzech wierzchołków przez krawędzie, a C i D są również połączone. Dwa sąsiednie węzły sąsiadują, jeśli są połączone krawędzią. Na rysunku przedstawiono typowy sposób budowania wykresów w informatyce. Kręgi reprezentują wierzchołki, a linie łączące ich parę to żebra.

Jaki wykres nazywa się non-oriented w informatyce? Jego związek między dwoma końcami żebra jest symetryczny. Żebro po prostu łączy je ze sobą. W wielu przypadkach jednak konieczne jest wyrażenie zależności asymetrycznych – na przykład fakt, że punkt A wskazuje na B, ale nie na odwrót. Celem tego jest definicja wykresu informatyki, który wciąż składa się z zestawu węzłów wraz z zestawem zorientowanych krawędzi. Każda zorientowana krawędź jest połączeniem wierzchołków, których kierunek ma wartość. Kierowane wykresy są reprezentowane w sposób pokazany na rysunku (b), ich krawędzie są reprezentowane strzałkami. Kiedy trzeba podkreślić, że wykres jest niekierunkowy, nazywa się on niekierowanym.

Modele sieci

Wykresy informatyki służą jako matematyczny model struktur sieciowych. Poniższy rysunek przedstawia strukturę Internetu, a następnie ARPANET w grudniu 1970 r., Kiedy miał tylko 13 punktów. Węzły są centrami obliczeniowymi, a krawędzie łączą dwa wierzchołki z bezpośrednim połączeniem między nimi. Jeśli nie zwracasz uwagi na nałożoną mapę Stanów Zjednoczonych, reszta obrazu to wykres 13-węzłowy podobny do poprzednich. W tym przypadku rzeczywiste rozmieszczenie wierzchołków jest nieistotne. Ważne jest, które węzły są ze sobą połączone.

Wykorzystanie wykresów w informatyce pozwala sobie wyobrazić, jak rzeczy są fizycznie lub logicznie ze sobą powiązane w strukturze sieci. 13-węzłowy ARPANET jest przykładem sieci komunikacyjnej, w której wierzchołki komputera lub inne urządzenia mogą transmitować wiadomości, a krawędzie są bezpośrednimi liniami, na których można przesyłać informacje.

Trasy

Choć wykresy są stosowane w wielu różnych obszarach, mają one wspólne cechy. Teoria wykresów (informatyki) zawiera, być może, najważniejsza – idea, że rzeczy często poruszają się wzdłuż krawędzi, konsekwentnie przechodząc z węzła na węzeł, niezależnie od tego, czy jest pasażerem kilku lotów czy informacji przekazywanych od osoby do osoby w sieci społecznościowej, czy też użytkownik Komputer, kolejno odwiedzając kilka stron internetowych, korzystając z linków.

Ten pomysł motywuje definicję trasy jako ciąg wierzchołków połączonych krawędziami. Czasami konieczne jest rozważenie trasy, która zawiera nie tylko węzły, ale również sekwencję łączących ich krawędzie. Na przykład sekwencja wierzchołków MIT, BBN, RAND, UCLA jest trasą na wykresie internetowym ARPANET. Przejście węzłów i krawędzi może być powtórzone. Na przykład SRI, STAN, UCLA, SRI, UTAH, MIT to także trasa. Ścieżka, w której krawędzie nie powtarzają się, nazywa się łańcuchem. Jeśli węzły nie są powtarzane, nazywany jest prostym łańcuchem.

Cykle

Szczególnie ważne typy wykresów w informatyce to cykle, które reprezentują strukturę pierścienia, taką jak sekwencja węzłów LINC, CASE, CARN, HARV, BBN, MIT, LINC. Trasy z co najmniej trzema krawędziami, w których pierwszy i ostatni węzeł są takie same, a inne są inne – cykliczne wykresy w informatyce.

Przykłady: cykl SRI, STAN, UCLA, SRI jest najkrótszy, a SRI, STAN, UCLA, RAND, BBN, UTAH, SRI jest dużo większy.

W rzeczywistości każda krawędź wykresu ARPANET należy do cyklu. Zostało to zrobione celowo: jeśli którykolwiek z nich nie powiedzie się, będzie można przenieść się z jednego węzła do drugiego. Cykle w systemach komunikacyjnych i transportowych są obecne w celu zapewnienia redundancji – zapewniają alternatywne trasy wzdłuż innej drogi ścieżki. W sieci społecznościowej cykle są często postrzegane. Kiedy na przykład okaże się, że bliską przyjaciółką żony twojej żony jest praca z bratem, jest to cykl, który składa się z ciebie, Twojej żony, kuzyna, przyjaciela szkoły, jego pracownika (tzn. Brother) i, wreszcie, znowu ty.

Połączony wykres: definicja (informatyka)

Jest rzeczą naturalną zapytać, czy można dostać z każdego węzła do jakiegokolwiek innego węzła. Wykres jest spójny, jeśli istnieje trasa między każdą parą wierzchołków. Na przykład sieć ARPANET jest połączonym wykresem. To samo można powiedzieć o większości sieciach komunikacyjnych i transportowych, ponieważ ich celem jest kierowanie ruchu z jednego węzła do drugiego.

Z drugiej strony, nie ma powodu a priori do spodziewania się, że takie typy wykresów w informatyce są szeroko rozpowszechnione. Na przykład w sieci społecznościowej nie trudno sobie wyobrazić dwie osoby, które nie są ze sobą połączone.

Komponenty

Jeśli wykresy z informatyki nie są połączone, to naturalnie ulegają rozkładowi w zestaw powiązanych fragmentów, grup węzłów, które są izolowane i nie przecinają się. Na przykład na rysunku pokazano trzy takie części: pierwszy – A i B, drugi – C, D i E, a trzeci – pozostałe wierzchołki.

Elementami łączenia wykresów są podzbiór węzłów, w których:

• Każdy wierzchołek podgrupy ma drogę do jakiejkolwiek innej;
• Podzbiór nie jest częścią większego zbioru, w którym każdy węzeł ma trasę do innego.

Kiedy wykresy w informatyce są podzielone na ich składniki, jest to tylko początkowy sposób opisu ich struktury. W obrębie tego składnika może istnieć bogata struktura wewnętrzna ważna dla interpretacji sieci. Na przykład formalną metodą określania znaczenia węzła jest określenie, ile części wykres dzieli się, jeśli węzeł zostanie usunięty.

Maksymalny składnik

Istnieje metoda jakościowej oceny elementów łączności. Na przykład istnieje ogólnoświatowa sieć społecznościowa z połączeniami między dwiema osobami, jeśli są przyjaciółmi.

Czy ona jest podłączona? Prawdopodobnie nie. Połączenie jest dość delikatną własnością, a zachowanie jednego węzła (lub jego małego zbioru) może go zniweczyć. Na przykład jedna osoba bez znajomych na żywo będzie komponentem składającym się z jednego wierzchołka, a zatem wykres nie będzie spójny. Lub zdalna tropikalna wyspa, składająca się z osób, które nie mają kontaktu z światem zewnętrznym, będzie również małym elementem sieci, co potwierdza niespójność.

Globalna sieć przyjaciół

Ale jest coś innego. Na przykład czytelnik popularnej książki ma przyjaciół, którzy dorastali w innych krajach i składają się na jeden z nich. Jeśli wziąć pod uwagę rodziców tych przyjaciół i ich przyjaciół, wszyscy ci ludzie są również w tym samym składniku, chociaż nigdy nie słyszeli czytelnika, mówią inaczej i nigdy nie byli z nim. W związku z tym, chociaż globalna sieć przyjaźni nie jest spójna, czytelnik wejdzie w bardzo duży składnik, który przeniknie do wszystkich części świata, w tym ludzi z bardzo różnych środowisk iw rzeczywistości zawiera dużą część populacji na świecie.

To samo dotyczy zestawów danych sieciowych – duże, złożone sieci często mają maksymalny składnik zawierający znaczną część wszystkich węzłów. Ponadto, gdy sieć zawiera maksymalny składnik, to prawie zawsze tylko jeden. Aby zrozumieć, dlaczego powinniśmy powrócić do przykładu z globalną siecią przyjaźni i spróbować wyobrazić sobie obecność dwóch maksymalnych składników, z których każdy obejmuje miliony ludzi. Wymaga to obecności pojedynczej krawędzi od jednego z pierwszych elementów do drugiego, tak aby dwa składniki maksymalne weszły w jeden. Ponieważ krawędź jest wyjątkowa, w większości przypadków jest niewiarygodna, że nie tworzy się, a zatem nigdy nie obserwuje się dwóch maksymalnych składników w rzeczywistych sieciach.

W rzadkich przypadkach, kiedy dwa komponenty maksymalnie współistniały przez długi czas w prawdziwych sieciach, ich zjednoczenie było nieoczekiwane, dramatyczne i ostatecznie miało katastrofalne konsekwencje.

Component Fusion Crash

Na przykład, po przybyciu europejskich badaczy do cywilizacji zachodniej półkuli, jakieś pół tysiącleca, nastąpił globalny kataklizm. Z sieciowego punktu widzenia wyglądało to tak: przez pięć tysięcy lat globalna sieć społeczna składała się prawdopodobnie z dwóch dużych elementów – jednego w Ameryce Północnej i Południowej, a drugiej w Eurazji. Z tego powodu rozwinęła się w sposób niezależny niezależnie od siebie w dwóch składnikach, a nawet gorszych chorobach ludzkich itp. Gdy oba komponenty nareszły się w końcu, technologie i choroby jednego z nich szybko i katastrofalnie wypełniły drugą.

American High School

Pojęcie maksymalnych komponentów jest przydatne do rozumowania sieci io wiele mniejszych rozmiarach. Ciekawym przykładem jest wykres ilustrujący romantyczne relacje w amerykańskiej szkole średniej przez 18 miesięcy. Fakt, że zawiera on maksymalny składnik, jest istotny w odniesieniu do rozprzestrzeniania się chorób przenoszonych drogą płci, co było celem badania. Uczniowie mogli mieć tylko jednego partnera na ten okres czasu, ale mimo to nie zdawali sobie sprawy z tego, że byli częścią maksymalnego składnika, a więc stanowią część wielu potencjalnych tras przesyłowych. Struktury te odzwierciedlają relacje, które od dawna już się skończyły, ale przez dłuższy czas wiążą się z osobnikami w łańcuchach, aby stać się przedmiotem bliskiej koncentracji i plotek. Są jednak realne: jako że fakty społeczne są niewidzialne, ale logicznie płynące makrostruktury, które powstały jako produkt indywidualnej mediacji.

Wyszukiwanie odległości i szerokości

Oprócz informacji o tym, czy dwa węzły są połączone trasą, teoria wykresów w informatyce umożliwia poznanie jej długości – w transporcie, komunikacji lub rozpowszechnianiu informacji i chorób, a także czy przechodzi przez kilka szczytów czy tłumów.

W tym celu określ długość trasy, równą liczbie kroków, które zawiera od początku do końca, czyli liczby krawędzi w sekwencji, która ją tworzy. Na przykład trasa MIT, BBN, RAND, UCLA ma długość 3, a MIT, UTAH wynosi 1. Używając długości ścieżki można powiedzieć, czy dwa węzły znajdują się na wykresie blisko siebie czy daleko: odległość między dwoma wierzchołkami jest określona jako długość Najkrótsza droga między nimi. Na przykład odległość między LINC i SRI wynosi 3, ale aby upewnić się z tego, należy upewnić się, że nie ma długości równej 1 lub 2 między nimi.

Algorytm wyszukiwania jest szeroki

Dla małych wykresów można łatwo obliczyć odległość między dwoma węzłami. Ale w przypadku złożonych, istnieje potrzeba systematycznej metody określania odległości.

Najbardziej naturalny sposób na to, a tym samym najbardziej skuteczny, jest następujący (na przykład globalnej sieci przyjaciół):

• Wszyscy przyjaciele są uznawani za znajdujących się w odległości 1.
• Wszyscy przyjaciele przyjaciół (nie licząc już oznakowanych) zostali ogłoszeni, aby znajdowali się w odległości 2.
• Wszyscy ich przyjaciele (znowu, nie licząc oznakowanych osób) są zadeklarowani na odległość w odległości 3.

Kontynuując w ten sposób wyszukiwanie jest przeprowadzane w kolejnych warstwach, z których każda jest większa niż poprzednia. Każda nowa warstwa składa się z węzłów, które jeszcze nie brały udziału w poprzednich i które wchodzą na krawędź z wierzchołkiem poprzedniej warstwy.

Ta technika nazywana jest wyszukiwaniem szerokości, ponieważ wyszukuje wykres na zewnątrz od węzła wyjściowego, przede wszystkim obejmując najbliższe. Oprócz ustalenia odległości, może służyć jako pożyteczna koncepcja organizacji struktury wykresu, jak również budować wykres w informatyce, umieszczając wierzchołki w oparciu o ich odległość od ustalonego punktu początkowego.

Wyszukiwanie szerokości można zastosować nie tylko do sieci przyjaciół, ale również do dowolnego wykresu.

Świat jest mały

Jeśli powrócisz do globalnej sieci znajomych, widać, że argument wyjaśniający własność maksymalnego składnika faktycznie mówi coś więcej: nie tylko czytelnik ma trasy do znajomych, które łączą go z dużą liczbą ludności świata, ale te trasy są niespodziewanie krótkie .

Ten pomysł był nazywany "zjawiskiem bliskiego świata": świat wydaje się mały, jeśli myślisz o tym, co krótka droga łączy dwie osoby.

Teoria "sześciu uścisk dłoni" została po raz pierwszy eksperymentowana przez Stanley Milgram i jego współpracowników w 1960 roku. Nie mając żadnych zestawów danych dotyczących sieci społecznościowych i budżetu w wysokości 680 dolarów, postanowił przetestować popularny pomysł. W tym celu poprosił 296 losowo wybranych inicjatorów, aby przesłały list do maklera, który mieszkał na przedmieściach Bostonu. Inicjatorom podano kilka osobistych informacji na temat celu (w tym adresu i zawodu) i musieli przekazać list osobie znanej imieniem i nazwiskiem, z tymi samymi instrukcjami, jak najszybciej osiągnął cel. Każda litera przeszła przez ręce wielu przyjaciół i utworzyła łańcuch, który zamknął się na brokerze wymiany poza Bostonem.

Wśród 64 łańcuchów, które osiągnęły cel, średnia długość wynosiła sześć, co potwierdziło liczbę o nazwie nazwanej dwadzieścia lat wcześniej w tytule sztuki Johna Garego.

Pomimo wszystkich wad tego badania eksperyment pokazał jeden z najważniejszych aspektów naszego zrozumienia sieci społecznych. W następnych latach podał szerszy wniosek: sieci społeczne z zasady mają bardzo krótkie drogi między dowolnymi parami ludzi. Nawet jeśli takie pośrednie związki z liderami biznesu i przywódcami politycznymi nie spłacają się codziennie, istnienie takich krótkich tras odgrywa dużą rolę w szybkości informacji, chorób i innych rodzajów infekcji w społeczeństwie, a także w możliwościach dostępu, które sieć społeczna zapewnia ludziom Całkowicie przeciwstawne cechy.