gráfelmélet
Mielőtt elkezdené tanulási algoritmusokkal közvetlenül, akkor kell egy alapvető ismereteket maguk grafikonok, hogy megérthesse képviselteti magát a számítógépet. Nem lesz részletesen minden szempontból gráfelmélet (ez nem kötelező), de csak azokat, amelyek a tudatlanság jelentősen megnehezítheti a felszívódását ez a programozás.
Néhány példa ad egy kicsit felszínes megértése a grafikon. Tehát egy tipikus grafikon a földalatti áramkör, vagy bármely más módon. Különösen a programozó ismeri a számítógép-hálózat, amely szintén egy gráf. Összességében van jelenlétében pontok vonalak kötik össze. Így egy számítógép a hálózaton - ezek külön szerverek, és a vonalak - különböző típusú elektromos jeleket. Az első metró - állomás, a második - az alagutakban, meghatározott közöttük. A gráfelmélet pontban nevezett csúcsok (csomópontok), és a vonalak - az élek (ívek). Így, a grafikon - egy sor csúcsok élek kötik össze.
Térjünk vissza a számítógépes hálózat. Ez egy bizonyos topológia és tetszőlegesen ábrázolható több számítógép és a hatásukat az összekötő. Az alábbi ábra egy példakénti teljesen csatlakoztatva topológia.
Ez lényegében a grafikonon. Öt csúcsok számítógépek, és a vegyület (jelzés útvonalon) között - a bordák. Tegye vissza a számítógép csomópontok, kapunk egy matematikai objektum - grafikon, amely 10 élek, és 5 csúcsot. Száma a csúcsokat lehet önkényesen, de nem feltétlenül úgy, ahogy megtörtént az ábrán. Meg kell jegyezni, hogy ebben a példában nem használ audio loop, azaz egy borda, amely kinyúlik a vertex és azonnal belép, de a hurkok előfordulhat a feladatokat.
Íme néhány fontos használt szimbólumok gráfelmélet:
- G = (V, E), a leírásban a G - grafikon, V - a csúcsait, és az E - borda;
- | V | - a sorrendben (csúcsok száma);
- | E | - a méret a grafikon (élek számát).
A mi esetünkben (. Ábra 1) | V | = 5, | E | = 10;
Amikor meg a felső bármely más vertex áll rendelkezésre, akkor ez a grafikon egy irányítatlan gráf (ábra. 1). Ha a gráf összefüggő, de ez nem így van, akkor az ilyen egy grafikon vagy digráf nevezzük orientált (ábra. 2).
A munkavégzés és irányítatlan gráfok van elképzelése, hogy milyen csúcsok. Fokú csúcsok - az élek száma csatlakoztatás más csomópontok. Az összeg az összes fok a gráfban egyenlő kétszer annyi éle. A 2. ábra esetében az összeg az összes fok 20.
A digráf, szemben egy irányítatlan gráf, lehetőség van arra, hogy mozgassa a tetejétől a felső s h nélkül közbenső csomópontok csak akkor, ha a borda ki h és benne van s, de fordítva nem.
Irányított gráf a következő formában:
G = (V, A), ahol V - felsők, A - irányított élek.
A harmadik típusú grafikonok - vegyes grafikonok (3. ábra). Ezek mind irányított élek és irányítatlan. Formálisan vegyes grafikon van írva, mint: G = (V, E, A), ahol az egyes betűk a zárójelben azt is, hogy a korábban tulajdonított.
A 3. ábrán látható grafikon egy ív irányított [(E, A), (E, C), (a, b), (c, a), (d, b)], mások - nem irányított [(e, d), (e, b), (d, c) ...].
Két vagy több grafikon első pillantásra tűnhet eltérő szerkezetű miatt előfordul, hogy a különböző képeket. De ez nem mindig van így. Vegyünk két a gráf (ábra. 4).
Azok megegyeznek egymással, mert a megváltoztatása nélkül egyetlen gráf struktúra lehet építeni egy másik. Az ilyen grafikonok izomorfak. t. e. rendelkeznek azzal a tulajdonsággal, hogy minden csúcs egy bizonyos számú élek a gráfnak azonos a másik tetejére. A 4. ábra mutatja a két izomorf grafikonok.
Amikor minden él van rendelve egy bizonyos értéket, az úgynevezett a súlya a bordák, majd a súlyozott gráf. A különböző problémák, mint a súly, hogy a különböző típusú mérések, mint például a hossza, az ár, stb útvonalak. N. Az grafikus ábrázolása a gráf feltüntetett tömeg értékek, jellemzően a szélek közelében.
Mindenesetre a grafikonok által megvizsgált minket a lehetőséget, hogy válassza ki az utat, és nem egy. Path - egy olyan szekvenciát csúcsok, amelyek mindegyike össze van kötve, hogy kövesse a borda. Ha az első és az utolsó csúcsai azonos, akkor ez az út az úgynevezett ciklust. A hossza határozza meg az összeg az alkotó élek. Például, ábra 4.a van szekvencia [(e), (a), (b), (c)]. Ez az út egy részgráf, mert tudjuk alkalmazni a meghatározását az utóbbi, azaz a gráf G '= (V', E ') egy részgráfja egy G = (V, E), csak akkor, ha V' és E „tartoznak V, E .
Módjai képviselő grafikonok
Graf, mint a legtöbb más matematikai objektumok is be kell mutatni a számítógépen (saját memóriájában tárolt). Számos módja van annak értelmezése, a leghíresebb közülük:
Az első két módszer magában tárolja a számlálás egy kétdimenziós tömb (mátrix). Ezen túlmenően, a mérete ezeknek a tömbök függ a csúcsok száma és / vagy a szélek egy adott oszlopban. Így szomszédsági mátrix mérete n × n, ahol n - a csúcsok számát és az előfordulási mátrix n × m, n - a csúcsok száma, m - az élek száma a gráfban.