Grafy v informatice: definice, typy, aplikace, příklady. Teorie grafů v informatice

Grafy v informatice jsou způsob definování vztahů v kombinaci prvků. To jsou hlavní předměty studia teorie grafů.

Základní definice

Co se skládá z grafu v informatice? Zahrnuje sadu objektů nazvaných vrcholy nebo uzly, z nichž některé páry jsou asociovány s tzv. žebra. Například graf na obrázku (a) se skládá ze čtyř uzlů, označené A, B, C a D, B, který je připojen ke každému z ostatních tří vrcholů žeber, a C a D jsou také spojeny. Dva uzly jsou sousední, pokud jsou spojeny okrajem. Obrázek ukazuje typický způsob, jak vytvořit grafy v oblasti výpočetní techniky. Kruhy reprezentují vrcholy a čáry, které spojují každou dvojici, jsou žebra.

Jaký graf se v počítačové vědě nazývá neorientovaný? Jeho vztah mezi oběma konci žebra je symetrický. Žebro je jednoduše spojuje mezi sebou. V mnoha případech je však nutné vyjádřit asymetrické vztahy - například, že A ukazuje na B, ale nikoliv naopak. Tento cíl je definován definicí grafu v informatice, který se stále skládá ze souboru uzlů spolu se sadou orientovaných okrajů. Každý orientovaný okraj je spojení mezi vrcholy, jejichž směr má hodnotu. Řízené grafy jsou znázorněny na obrázku (b), jejich okraje jsou znázorněny šipkami. Když je třeba zdůraznit, že graf je nesměrový, nazývá se neorientovaný.

Modely sítí

Grafy v informatice slouží matematický model síťové struktury. Následující obrázek znázorňuje strukturu internetu, poté nazývanou ARPANET, v prosinci 1970, kdy měla pouze 13 bodů. Uzly jsou výpočetní centra a okraje spojují dva vrcholy s přímým spojením mezi nimi. Pokud nevěnujete pozornost nadřazené mapě USA, zbytek obrazu je graf 13 uzlů podobný předchozímu. V tomto případě je skutečné uspořádání vrcholů nevýznamné. Důležité je, které uzly jsou navzájem propojeny.

Použití grafů v počítačové vědě vám umožňuje představit, jak jsou věci ve struktuře sítě fyzicky nebo logicky spjaty. 13-uzelový ARPANET je příklad komunikační sítě, ve které mohou počítačové vrcholy nebo jiná zařízení vysílat zprávy a hrany jsou přímé odkazy, přes které mohou být informace přenášeny.

Trasy

Přestože se grafy používají v mnoha různých oblastech, mají společné rysy. teorie grafů (počítačová věda) zahrnuje snad nejdůležitější z nich - představa, že věci se často pohybují podél okrajů, postupně pohybující se od uzlu k uzlu, ať už se jedná o cestující pár lety nebo informace předávané z člověka na člověka v sociální síti, nebo uživatel počítač, postupně navštěvovat řadu webových stránek, následovat odkazy.

Tato myšlenka motivuje definici trasy jako posloupnosti vrcholů spojených okraji. Někdy je nutné zvážit trasu, která obsahuje nejen uzly, ale i sekvenci okrajů, které je spojují. Například sekvence vrcholů MIT, BBN, RAND, UCLA je trasa v internetovém grafu ARPANET. Průchod uzlů a hran může být opakován. Například SRI, STAN, UCLA, SRI, UTAH, MIT jsou také cestou. Cesta, ve které se hrany neopakují, se nazývá řetězec. Pokud se uzly neopakují, nazývá se jednoduchým řetězcem.

Cykly

Zvláště významné druhy v počítačových grafů - IT cykly, které představují cyklickou strukturu, jako je například sekvence uzlů LINC, případě, Karn, HARV, BBN, MPO, LINC. Trasy s nejméně třemi okraji, ve kterých jsou první a poslední uzly stejné a jiné jsou jiné, jsou cyklické grafy v informatice.

Příklady: cyklus SRI, STAN, UCLA, SRI je nejkratší a SRI, STAN, UCLA, RAND, BBN, UTAH, SRI je mnohem větší.

Ve skutečnosti každý okraj grafu ARPANETu patří do cyklu. To bylo provedeno úmyslně: pokud některý z nich selže, zůstane možnost přechodu z jednoho uzlu na druhý. Cykly v komunikačních a dopravních systémech poskytují redundanci - poskytují alternativní cesty podél jiné dráhy cesty. V sociální síti jsou často vidět také cykly. Když zjistíte, například, že blízký přítel ze školy bratrance své ženy ve skutečnosti pracuje se svým bratrem, je to cyklus, který se skládá z vás, vaše manželka, její bratranec, jeho přítel ze školy, jeho zaměstnance (např. E. Your bratr) a nakonec znovu.

Připojený graf: definice (informatika)

Je přirozené se ptát, zda je možné se dostat z každého uzlu do jiného uzlu. Graf je koherentní, jestliže existuje cesta mezi každou dvojicí vrcholů. Například síť ARPANET je připojený graf. Totéž lze říci o většině komunikačních a dopravních sítí, protože jejich cílem je řídit provoz z jednoho uzlu do druhého.

Na druhou stranu neexistuje a priori žádný důvod očekávat, že tyto druhy grafů v informatice jsou rozšířené. Například v sociální síti není obtížné si představit dva lidi, kteří nejsou navzájem propojeni.

Komponenty

Pokud nejsou grafy v informatice spojeny, pak se přirozeně rozkládají do souboru souvisejících fragmentů, skupin uzlů, které jsou izolované a nepřekrývají se. Například obrázek ukazuje tři takové části: první - A a B, druhé - C, D a E a třetí se skládá ze zbývajících vrcholů.

Komponenty připojení grafu jsou podmnožinou uzlů, které mají:

• každý vrchol podskupiny má cestu k jinému;
• Podskupina není součástí většího souboru, ve kterém má každý uzel cestu k jinému.

Když jsou grafy v počítačové vědě rozděleny do jejich složek, je to pouze počáteční způsob, jak popisovat jejich strukturu. V rámci této komponenty může existovat bohatá vnitřní struktura, důležitá pro interpretaci sítě. Například formální metodou určení významu uzlu je určit, kolik částí se graf dělí, pokud je uzel odstraněn.

Maximální součást

Existuje metoda kvalitativního vyhodnocování komponent konektivity. Existuje například celosvětová sociální síť s propojením mezi dvěma lidmi, pokud jsou přátelé.

Je spojena? Pravděpodobně ne. Spojení je poměrně křehká vlastnost a chování jednoho uzlu (nebo malého souboru) může způsobit jeho zničení. Například jedna osoba bez živých přátel bude součástí složený z jediného vrcholu, a proto graf nebude spojen. Nebo také vzdálený tropický ostrov, který se skládá z lidí, kteří nemají žádný kontakt s vnějším světem, bude také malou součástí sítě, což potvrzuje její nesoudržnost.

Globální síť přátel

Ale je tu ještě něco. Například čtenář oblíbené knihy má přátele, kteří vyrůstali v jiných zemích a tvoří s nimi jednu složku. Pokud vezmete v úvahu rodiče těchto přátel a jejich přátel, pak všichni tito lidé jsou také ve stejné složce, ačkoli oni nikdy neslyšeli o čtenáři, mluvili jiným jazykem a nikdy nebyli s ním. Tedy, i když globální síť přátelství - není připojena čtečka budou zahrnuty ve složce jsou velmi velké, proniká do všech koutů světa, která zahrnuje lidi z mnoha různých prostředí a ve skutečnosti obsahuje významnou část světové populace.

Totéž platí pro datové sady v síti - velké, složité sítě mají často maximální součást, která zahrnuje významnou část všech uzlů. Kromě toho, pokud síť obsahuje maximální komponentu, je téměř vždy jen jedna. Abychom pochopili, proč bychom se měli vrátit k příkladu s globální sítí přátelství a pokusit se představit přítomnost dvou maximálních složek, z nichž každý zahrnuje miliony lidí. Bude vyžadovat přítomnost jediného okraje z jedné z prvních součástí na druhou, aby se obě maximální součásti spojily do jednoho. Vzhledem k tomu, že okraj je jedinečný, je ve většině případů neuvěřitelné, že se netvoří, a proto se oba maximální součásti v reálných sítích nikdy nevidí.

V některých ojedinělých případech, kdy dvě maximální součásti dlouhodobě koexistovaly v reálné síti, jejich sjednocení bylo neočekávané, dramatické a nakonec mělo katastrofické následky.

Spojení součástí

Například po příchodu evropských vědců do civilizace na západní polokouli před zhruba půl tisíciletími došlo k celosvětové katastrofě. Z pohledu sítě to vypadalo takto: pět tisíc let globální sociální síť pravděpodobně tvořila dvě obří součásti - jedna v Severní a Jižní Americe a druhá v Eurasii. Z tohoto důvodu je tato technologie se vyvinula nezávisle v obou složek, a ještě horší, as vyvinula a lidská nemoc, a tak dále. D. Když se obě složky se konečně dostal na dotykové technologie a nemoc rychle a katastrofálně přetekl druhý.

Americká střední škola

Koncept maximálních komponent je užitečný pro úvahy o sítích a mnohem menších velikostech. Zajímavým příkladem je graf ilustrující romantický vztah v americké střední škole po dobu 18 měsíců. Skutečnost, že obsahuje maximální složku, je důležitá, pokud jde o šíření pohlavně přenosných chorob, což bylo cílem studie. Žáci mohou mít pro toto období pouze jednoho partnera, nicméně bez toho, aby si to uvědomili, byli součástí maximální složky a tudíž součástí mnoha potenciálních přenosových cest. Tyto struktury odrážejí vztahy, které mohou dávno skončit, ale propojují jednotlivce v řetězcích příliš dlouho, aby se staly předmětem pečlivé pozornosti a drby. Nicméně jsou skutečné: jelikož společenské fakty jsou neviditelné, ale logicky tekoucí makrostruktury, které vznikly jako produkt individuálního zprostředkování.

Vyhledávání vzdálenosti a šířky

Kromě informací o tom, zda jsou dva uzly spojeny cestou, teorie grafů v informatice vám umožní seznámit se s jeho délkou - v oblasti dopravy, komunikace a šíření zpráv a nemoci, stejně jako to, zda jde přes několik vrcholů nebo násobku.

K tomu, definují délku trasy, která se rovná počtu kroků, které obsahuje, od začátku až do konce, tj. E. počet hran v posloupnosti, která je. Například, MPO, BBN, RAND, UCLA trasa má délku 3, a MPO, Utah - 1. Pomocí délku dráhy, lze říci, že pokud dva uzly jsou uspořádány ve sloupci blízko u sebe, nebo velké vzdálenosti mezi dvěma vrcholy je definována jako délka nejkratší cestu mezi nimi. Například, vzdálenost mezi LINC a SRI je 3, i když, aby zajistily to, že je nezbytné ověřit nepřítomnost délce rovnající se 1 nebo 2, mezi nimi.

Algoritmus vyhledávání ve šířce

U malých grafů lze vzdálenost mezi dvěma uzly snadno vypočítat. Pro složité je však potřeba systematická metoda určování vzdáleností.

Nejpřírodnějším způsobem, jak to udělat a tudíž nejúčinnější, je následující (na příkladu globální sítě přátel):

• Všichni přátelé jsou prohlášeni za vzdálenost 1.
• Všichni přátelé přátel (s výjimkou těch, kteří již byli označeni) jsou deklarováni, že se nacházejí ve vzdálenosti 2.
• Všichni jejich přátelé (znovu, bez počítání označených osob) jsou prohlášeni vzdáleni ve vzdálenosti 3.

Tímto způsobem se vyhledávání provádí v následujících vrstvách, z nichž každá je jedna jednotka za předchozí. Každá nová vrstva se skládá z uzlů, které se dosud nezúčastnily, a které vstupují na okraj s vrcholem předchozí vrstvy.

Tato technika se nazývá vyhledání šířky, protože vyhledává graf směrem ven od počátečního uzlu, nejprve pokrývá nejbližší. Vedle poskytnutí způsobu určení vzdálenosti může sloužit jako užitečný koncepční základ pro organizaci struktury grafu, jakož i pro sestavení grafu v informatice a umístění vrcholů na základě jejich vzdálenosti od stanoveného počátečního bodu.

Šířka vyhledávání může být použita nejen pro síť přátel, ale i pro libovolný graf.

Svět je malý

Vydáte-li se zpět do celosvětové sítě přátel, můžete vidět, že argument, který vysvětluje, patřící do nejvyšší složky skutečně schválí něco víc: nejen čtenář má trasy s přáteli, spojující ho s výrazným podílem světové populace, ale tyto cesty jsou překvapivě krátká .

Tento nápad se nazýval "fenomén blízkého světa": svět vypadá jako malý, pokud se zamyslíte nad tím, jaká krátká cesta spojuje dva lidi.

Teorie „šesti potřesení rukou“ byla poprvé experimentálně zkoumána Stanley Milgram a jeho kolegové v roce 1960. Aniž by si sadu dat sociální sítě a s rozpočtem ve výši $ 680 se rozhodl vyzkoušet populární představu. Za tímto účelem požádal 296 náhodně vybraných iniciátory pokusu odeslat dopis na makléře, který žil na předměstí Bostonu. Iniciátory dostali nějaké osobní informace o účelu (včetně adresy a profese), a oni museli poslat dopis osobě, kterého znal jménem, ​​se stejnými instrukcemi, aby se dosáhlo cíle tak rychle, jak je to možné. Každé písmeno prošlo rukama několika kamarády a vytvoří řetěz se uzavře pro makléři ven z Bostonu.

Mezi 64 řetězci, které dosáhly cíle, průměrná délka byla šest, což bylo potvrzeno číslem vypsaným dvěma desetiletími dříve v titulu hry John Gare.

Přes všechny nedostatky této studie, experiment prokázal jeden z nejdůležitějších aspektů našeho chápání sociálních sítí. V letech, která následovala z ní byl proveden širší závěr: sociální sítě mívají velmi krátké cesty mezi libovolnými dvojicemi lidí. A i když tyto nepřímé spojení s podnikateli a politickými vůdci nemusí platit za sebe na denní bázi, je existence takových krátkých tratích hraje velkou roli v rychlosti šíření informací, nemoc a jiné typy infekcí v komunitě, stejně jako přístup k možnosti, že sociální sítě umožňují uživatelům naprosto opačné kvality.