Alapvető gráfelméleti alapfogalmak
Alapvető gráfelméleti alapfogalmak
Formálisan, a grafikon egy rendezett pár, G = (V, E) a készletek, amelyek közül az első áll csúcsok vagy csomópontok a gráf, és a többi - az éle. Egy él köti össze a két csúcsot. Amikor dolgozik grafikonok gyakran vagyunk kíváncsiak, hogy hogyan, hogy előkészítsék az utat az élek egyik csúcsa a másikra. Ezért fogunk beszélni a mozgás a széle; ez azt jelenti, hogy haladunk a csúcsából a grafikon egy másik B csúcs társított egy él AB (gráf összekötő él két csúcsot, a rövidség kedvéért jelöljük ezt a pár csúcsok). Ebben az esetben azt mondjuk, hogy egy szomszédos B, illetve, hogy a két szomszédos csúcs.
Egy gráf orientációjú lehet, vagy nem. A bordák irányítatlan gráf, gyakran nevezik egyszerűen számolni, akkor mehet mindkét irányban. Ebben az esetben egy él - egy rendezetlen pontpár, a végeit. Egy irányított gráfban, vagy digráf, az élek vannak rendezett párokat csúcsok: az első csúcs - a felső él, és a második - a végén. Továbbá, az egyszerűség kedvéért egyszerűen beszélni a széleket, és a fókuszálás, vagy nem lesz világos a háttér.
Később, akkor egyszerűen felhívni grafikonok és nem kér sokat közülük. Csúcsok kerülnek körök jelzik, és a széleket - vonalszakaszok. Bent a körök lesz írva vertex címkéket. A bordák irányított gráf fognak nyújtani, nyilakkal jelölve a megengedett haladási irány mentén.
Az 1. ábra grafikus ábrázolása egy irányítatlan (a) és orientált (b) ábrával együtt formális leírása.
terminológia
Teljes Count - egy grafikont, amelyben minden csúcs össze van kötve mindenki másnak. A élek száma egy teljes gráf hurok nélkül n csúcsú egyenlő (N 2 - N) / 2. A teljes orientirvoannom dobozban hagyjuk az átmenet minden csomópont minden más. Mivel az átmenet gráf él megengedett mindkét irányban, és a folyosón egy él a digráf - csak egy, a teljes digráf kétszer bordák, azaz számuk egyenlő N 2 - N.
Részgráf (VS. ES) grafikon vagy digráf (V, E) egy részhalmaza csúcsok és egy részhalmazát élek összekötő őket.
Path a grafikont, vagy irányított gráf - sorozata élek, amely viszont sor. Más szóval, az út a vertex csúcsából B kezdődik A és áthalad a sor bordák mindaddig, amíg a csúcs eléréséig B. formális szempontból, az utat a felső vertex vj vi egy szekvencia élek vi vi + 1. vi + 1, vi + 2. vj-1, vj. Követeljük, hogy minden csúcs találkozott ilyen módon legfeljebb egy alkalommal. Minden út hossza - az élek számát is. A hossza AB, BC, CD, DE egyenlő 4.
Egy súlyozott gráf vagy digráf minden éle hozzárendelt nevezett szám a súlya a szélét. Ha a kép általában rögzített gráf élei szélén súlyát. A hivatalos leírást a súlya lesz egy további elemet rendezetlen, vagy rendezett pár, a csúcsok (képezve azzal ez a pár, „t”). Ha a munka a irányított gráfok figyelembe vesszük a uszonyok súlya át az ár rajta. Az út költsége súlyozott gráf súlyok összege az élek az út. A legrövidebb út egy súlyozott gráf - ez az út és minimális súly, akkor is, ha az élek száma az utat, és csökkenteni lehet. Ha például, útvonal P1 tartalmaz öt darab bordával, a teljes tömeg 24, és az út P2 - három élének egy teljes súlya 36, akkor az útvonal P1 minősül rövidebb.
Egy gráf vagy digráf van csatlakoztatva, ha minden pár csomópont csatlakoztatható legalább egy módját. Cycle - olyan út, amely kezdődik és végződik ugyanabban csúcs. Az aciklikus gráf vagy digráf ciklus áll rendelkezésre. A gráf aciklikus nevezzük (gyökértelenséget) fa. Nem gyökeres fa struktúra ugyanaz, mint a fa, csak nincs kiválasztva gyökér. Azonban minden csúcs gyökeres fa is lehet a gyökere.