6. Irányított és irányítás nélküli gráfok Flashcards
Irányított és irányítás nélküli gráfok
Irányított gráf: a csúcsok közötti kapcsolatnál számít a kapcsolat iránya
Tetszőleges $V \neq ∅$ nemüres halmaz és $E⊆ V^2$ esetén a $G:=(V,E)$ algebrai struktúrát irányított gráfnak nevezzük. E elemei irányított élek.
Irányítatlan gráf: nem számít a kapcsolat iránya, csak a kettő közötti létező kapcsolatot írja le
$G=(V,E,f)$ hármast értjük, ahol V nemüres halmaz, E tetszőleges halmaz, f pedig tetszőleges leképezés. Tetszőleges $e ∈E$ élre, $e_i = {x, y}$, akkor x-t, y-t az e él 2 végpontjának nevezzük.
N-csúcsú teljes gráf:
Tetszőleges $n \in \N$ , $n \geq 1$ természetes szám esetén
$K_n = (V,E)$ ahol $|V| = n$ és $E = [V]^2$,
azaz az összes lehetséges (egyszeres és nem hurok) élt behúztuk a n csúcs között.
Kétpólusú gráf:
A G=( V,E) gráfot kétpólusú vagy páros gráfnak nevezzük, ha V csúcshalmaza felbontható két nemüres részre (pólusok), úgy, hogy élek csak különböző pólusok között húzódhatnak, azaz
$V=A \cup B$, $A \cap B = \emptyset$ $A,B \neq \emptyset$ és
$E \subseteq { { a,b } :a \in A, b \in B }$
Egyszerű gráfok:
- A $G=(V,E)$ gráfot egyszerű gráfnak nevezzük, ha nincs benne sem hurokél, sem többszörös él.
- Tetszőleges G=(V,E) egyszerű gráf komplementer gráfja a következő $¬G=(V,¬E), ¬E=\frac{[V]^2}{E}$,
azaz ${x,y}∈ ¬E ⇔ {x,y}\notin E (x,y∈V)$
(itt a negált jelek az adott szimbólum fölötti vonással van a könyvben jelölve.)
Utak
- $P_n$ jelöli az $n$-hosszú utat tetszőleges $n∈ N, n ≥ 1$ természetes számra, ahol $P_n=(V,E)$,
$V={a_0, a_1, …, a_n}$ és $E={{a_i
, a_{i+1}} : 0 ≤ i < n}$. Amennyiben kikötjük a csúcsok különbözőségét, egyszerű útról beszélünk.
Körök
- $C_n$ jelöli az $n$-hosszú kört tetszőleges $n∈ \N , n ≥ 1$ természetes számra, ahol $C_n$ egy olyan $n$-hosszú út, ahol az első és az utolsó csúcs megegyezik: $a_n = a_0$. Amennyiben ettől eltekintve a többi csúcs mind különböző, akkor egyszerű körről beszélünk.
Fokszám:
- Legyen $G=(V,E)$ egy tetszőleges gráf. G csúcsainak fokszáma
$δ(v) := \sum_{v∈e,}m(e) + \sum_{
v∈e,e hurokél}m(e)$,
és ha a gráfban nincs többszörös él, akkor a fenti képlet az alábbi módon is írható:
$δ(v) := \sum_{v∈e,}1 + \sum_{
v∈e,e hurokél}1$ - V csúcs izolált ha $δ(v) = 0$
Részgráf
- Legyen $G(V,E)$ tetszőleges gráf. Ekkor a $H=(W,F)$ gráf részgráfja a G-nek, ha $W⊆V$ és $F⊆ E$, azaz $∀x,y∈W ∈ {x, y} ∈ F$ ⇒ ${x, y} ∈ E$ és többszörös élek esetén $∀e ∈ E$ $m_H(e) ≤ m_G(e)$. Jele: $H ⊆G$.
Feszített részgráf:
Egy $( H = (W, F) )$ gráfot a $( G = (V, E) )$ gráf feszített részgráfjának nevezünk, ha a következő feltételek teljesülnek:
- Csúcsok: $( W \subseteq V )$, azaz $( H )$ csúcsai a $( G )$ csúcshalmazának részhalmazai.
-
Élek: Két csúcs $( x, y \in W )$ között akkor és csak akkor van él $( H )$-ban, ha ezek között él van $( G )$-ben is.
- Formálisan: $( {x, y} \in F )$ pontosan akkor, ha $( {x, y} \in E )$.
- Többszörös élek (ha vannak): Minden él $( e \in E )$ esetén $( m_H(e) = m_G(e) )$, ahol $( m_H(e) )$ és $( m_G(e) )$ az $( e )$ él multiplicitását jelölik $( H )$-ban és $( G )$-ben.
G gráfnak akkor feszített részgráfja H, hogyha minden olyan közös csúcsuk között lévő él megtalálható H-ban, ami G-ben is.
Összefüggőség
Egy tetszőleges $G=(V,E)$ gráf összefüggő, ha bármely $v_1, v_2 ∈ V$ csúcsai között van út.
Komponensek
Legyen $G=(V,E)$ tetszőleges gráf. $G$ maximális összefüggő részgráfjait a gráf komponenseinek hívjuk.
Tintacsöppentő algoritmus a gráf komponenseinek megkeresésére:
A gráf egyik $v_0$ csúcsába kék tintát csöppentve az először $v_0$ szomszédait festi kékre, az éleken szétfolyva, majd tovább folyva a szomszédok szomszédait, és így tovább. Mivel a gráf véges, előbb-utóbb a kék tinta terjedése megáll. Ha a gráf összes csúcsa kék, akkor a gráf összefüggő. Ha nem minden csúcs kék, akkor a kék csúcsok alkotják a gráf egyik, a $v_0$ csúcsot tartalmazó komponensét. Ekkor választunk egy tetszőleges, nem kék $v_1$ csúcsot, amelyre piros tintát csöppentve megkapjuk a $v_1$-et tartalmazó komponenst. Majd a sárga, zöld…, $i≤ k$ komponenst. Az algoritmust, pontosabban a tinták terjedését csúcsmátrix segítségével könnyen nyomon követhetjük.
Euler tétel I.
Tetszőleges G gráfban pontosan akkor van Euler-kör, ha a gráf összefüggő és minden csúcs fokszáma páros.
Euler tétel II.
Tetszőleges G gráfban pontosan akkor van Euler-út, ha a gráf összefüggő és a páratlan fokú csúcsok száma 0 vagy 2.
Algoritmus Euler-körök keresésére:
Induljunk ki egy tetszőleges $x_0 ∈V$ csúcsból, egymás után válasszunk ki egymáshoz kapcsolódó éleket. A kiválasztott éleket távolítsuk el a gráfból, és minden lépésben a legutolsó kiválasztott élhez csatlakozó élek közül válasszunk ki egy nem elvágót (aminek elhagyása után a megmaradt gráf még mindig összefüggő marad).
