„Gráfelméleti fogalomtár” változatai közötti eltérés

→‎Összefüggőség: elvágó (''cut'') / elválasztó (''separating'') csúcs/él mizéria
(→‎Összefüggőség: elvágó (''cut'') / elválasztó (''separating'') csúcs/él mizéria)
Ha egy gráfban bármely két csúcs között van út, akkor a gráfot '''összefüggő'''nek hívjuk.
 
Egy '''összefüggő komponens''' (vagy ''komponens'') egy maximális összefüggő részgráf. Az összefüggő gráfok egyetlen komponensből állnak, míg a nem összefüggők legalább kettőből. A ''G'' gráf komponenseinek számát ''C''(''G'')-vel jelöljük.
 
 
'''Csúcsok'''
 
Egy '''elvágó pont''' (''artikulációs pont'') egy olyan csúcsa egy összefüggő gráfnak, amelynek elhagyásával a megmaradó részgráf már nem összefüggő (''szétesik''; egy csúcsot mindig csak a vele szomszédos élekkel együtt lehet elhagyni). Például egy fa összes belső csúcsa elvágó pont. Egy '''elvágó ponthalmaz''' csúcsok egy olyan halmaza, melyek elhagyásával a maradék gráf szétesik. Az ''elvágó él''et hasonlóan definiáljuk (lásd alább).
 
Ha találunk utat a gráfban bármely két csúcs között még tetszőleges ''k'' &minus; 1 csúcs elhagyása után is, akkor a gráfot '''''k''-szorosan összefüggő'''nek hívjuk. Vegyük észre, hogy egy gráf akkor és csak akkor ''k''-szorosan összefüggő, ha bármely két csúcs között van ''k'' diszjunkt (''pontidegen'') út. A példa gráf összefüggő tehát, 1-szeresen összefüggő, de nem 2-szeresen összefüggő. A ''G'' gráf '''összefüggőség'''e (?: 'connectivity'; jelölése κ(''G'')) az a legkisebb szám, ahány csúcs elhagyásával a gráf szétesik. Konvenció szerint ''K''<sub>''n''</sub> teljes gráf összefüggősége ''n'' &minus; 1; és az üres gráf összefüggősége 0.
 
Egy '''elválasztó pont''' (?: 'separating'szeparáló vertexpont'') olyan csúcsa egy gráfnak amelynek elhagyásával a gráf komponenseinek száma növekszik. Azaz egy elválasztó pont valamelyik komponens elvágó pontja. Például az erdők összes belső csúcsa elválasztó pont.
 
 
'''Élek'''
 
Egy '''elvágó él''', vagy '''híd''' egy olyan él egy összefüggő gráfban, melynek elhagyásával a gráf már nem marad összefüggő. Például a fák minden éle hídelvágó él. Egy '''elvágó élhalmaz''' egy olyan élek halmaza, melyek elhagyásával a gráf komponenseineknem összefüggő gráfra számaesik növekszikszét. Egy '''vágás''' az összes olyan él halmaza, melyeknek egyik végpontja egy adott ''S'' csúcsrészhalmazban található, míg a másik végpontjuk ''V''(''G'')\''S''-beli. Például ''K''<sub>3</sub> élei elvágó élhalmazt alkotnak, de vágást nem. Bármely két él ''K''<sub>3</sub>-ban minimális elvágó élhalmazt és ugyanakkor vágást is alkotnak. Egy vágás mindenképpen elvágó élhalmaz is; és egy minimális elvágó élhalmaz mindig vágás is egyben (nemüres gráfban).
 
Egy '''elválasztó él''' vagy '''híd''' (''szeparáló él'') egy olyan él egy nem feltétlenül összefüggő gráfban, melynek elhagyásával a gráf komponenseinek száma növekszik, azaz egy híd valamelyik komponens elvágó éle. Pélául az erdők minden éle híd.
<!--
A bond is a minimal (but not necessarily minimum), nonempty set of edges whose removal disconnects a graph. A cut vertex is an analogous vertex (see above).-->
Az ''elvágó pont''ot hasonlóan definiáljuk (lásd feljebb).
 
Egy gráf '''''k''-szorosan élösszefüggő''', ha bármely ''k'' &minus; 1 él elhagyásával is összefüggő marad. Egy gráf '''élösszefüggőség'''e (jelölése κ’(''G'')), azon élek minimális száma, melyek elhagyásával ''G'' már nem marad összefüggő. Jól ismert eredmény, hogy κ(''G'') ≤ κ’(''G'') ≤ δ(''G'').
321

szerkesztés