Csúcsok, élek (ívek), grafikonok - studopediya
A készlet V csúcsok és több linkek a készlet E közöttük az úgynevezett gráf és kijelölt G (V. E).
Ábra. 2.1 ábra példát mutat a G gráf (4,6), ahol jelezzük:
n = | V | = 4 - a csúcsok száma a G (4,6),
m = | E | = 6 - száma élek a G gráf (4,6).
E - a feltérképezése V-V (E. VV).
Előfordul, hogy a készlet E egy család kommunikáció, mint E lehetnek irányított és nem irányított kommunikációs hurok, és ezek mind többszöröse, míg halmazelmélet, ugyanazokat az elemeket képviselik egyetlen tagja.
Egy másik példa, ábra. 2.2 családját mutatja gráfok négy csúcsot.
Ügyeljen arra, hogy a közös jelölés bizonyos grafikonok:
K4 - teljes gráf benne minden csúcsában van egy kapcsolat a többi csúcsot.
Általában, az ilyen típusú grafikonok a következőképpen jelöljük:
Felhívjuk a figyelmet, hogy a gróf C4. Ez a grafikon lehet képviselt, és ábrán látható. 2.3. Egy ilyen görbét jelzi K2,2 nevezik teljes páros gráf.
A páros gráf csúcshalmaza V feloszthatjuk két részhalmazát X és Y, oly módon, hogy a csúcsok között belül valamennyi közülük linkek. A élek száma a teljes páros gráf m = n1n2. ahol n1 = | X |, n2 = | Y |, n = n1 + n2.
Ha a kapcsolat iránya van, ez az úgynevezett ív, egyébként - él. (Grafikonok ívek és a bordák ábrán látható. 2.4).
Amikor szükséges, egy adott ív (él) jelöli a megfelelő nevet, vagy egy pár csúcsok kerek (direkt) zárójelben e = (V1, V2) - arc e, (e = [v1, v2] - e borda).
Egy grafikont, amelyben az összes kötések bordák, irányítatlan gráf nevezzük rövidített neorgrafom (ábra. 2.4 a).
Egy gráf ívekkel úgynevezett irányított gráf vagy digráf (ábra. 2.4, b).
Egy él (ARC), amelynek mindkét vége társított azonos vertex nevezzük hurok (ábra. 2.5).
Ha több széleit a grafikont, azaz Néhány összekötő élek pontosan ugyanaz a pár csúcsok, a grafikon nevezzük multigráf. Ha minden multigráfra élek azonos sokfélesége k. Egy ilyen gráfot nevezzük k-szoros, vagy csak k-gráf. Ábra. 2.6 mutatja multigráf G (6,20):
Egy gráf nevezzük pseudographs ha a beállított E magában bordák, ívek, hurkok, és azok mind többszörösei (ábra. 2.7).
Két csúcsot nevezik szomszédos, ha van összekötve néhány él (ív), és két különböző él (ívek) szomszédos, ha van közös csúcsa. Ábra. 2.8 A G gráf (3,3) a szomszédos csúcsok és b; a és c; b és c. valamint a kapcsolódó ív E2 és E3. szomszédos élei E1 és E2 ív. szomszédos élei E1 és E3 ív.
Két csúcsot nevezik szomszédos, ha van összekötve néhány él (ív), és két különböző él (ívek) szomszédos, ha van közös csúcsa. Ábra. 2.8 A G gráf (3,3) a szomszédos csúcsok és b; a és c; b és c. valamint a kapcsolódó ív E2 és E3. szomszédos élei E1 és E2 ív. szomszédos élei E1 és E3 ív.
X esemény csúcsa él (ív) e. Ha ez az elején vagy végén élek (ívek). Ábra. 2.8 csúcsok a és b incidens szélén e1. csúcsok b és c eset e2 ív.
Az ív (él) e beeső csúcsok x. ha kijön a felső vagy annak egy részét. Ábra. 2.8 ív e2 esemény csúcsa b és c.