Részgráfok, izomorfizmus, séták és utak

Definíció — részgráf

A \(G' = (V', E', \varphi')\) gráf a \(G = (V, E, \varphi)\) gráf részgráfja, ha \(V' \subseteq V\), \(E' \subseteq E\) és \(\varphi' = \varphi|_{E'}\) (a megmaradó élek végpontjai amik \(G\)-ben voltak).

Definíció — feszítő részgráf

A \(G\) gráfnak \(G'\) feszítő részgráfja, ha részgráfja \(G\)-nek és \(V(G') = V(G)\).

Definíció — feszített részgráf

Legyen \(G\) gráf, \(\emptyset \neq X \subseteq V(G)\). Ekkor az \(X\) által feszített részgráf az a részgráf, melynek csúcshalmaza \(X\), és tartalmaz minden olyan élt, aminek mindkét végpontja \(X\)-beli.

Tétel — részgráfok előállítása

1. \(G'\) részgráfja \(G\)-nek \(\iff\) \(G'\) véges sok csúcs és él törlésével adódik \(G\)-ből.
2. \(G'\) feszítő részgráfja \(G\)-nek \(\iff\) \(G'\) véges sok él törlésével adódik \(G\)-ből.
3. \(G'\) feszített részgráfja \(G\)-nek \(\iff\) \(G'\) véges sok csúcs törlésével adódik \(G\)-ből.

Definíció — klikk

Egy gráfban egy teljes részgráfot klikknek nevezünk.

Definíció — klikkméret

Egy \(G\) gráf max klikkmérete a legtöbb csúcsot tartalmazó klikkjének csúcsszáma. Jelölése: \(\omega(G)\) (ómega).

Definíció — gráfok izomorfizmusa

A \(G = (V, E, \varphi)\) és \(G' = (V', E', \varphi')\) gráfok izomorfak, ha \(\exists f: V \to V'\) bijektív függvény és \(\exists g: E \to E'\) bijektív függvény, amelyek illeszkedéstartók: azaz, ha \(e \in E\) és \(\varphi(e) = \{v, w\}\), akkor \(\varphi'(g(e)) = \{f(v), f(w)\}\). Jelölés: \(G \cong G'\).

Tétel

Ha \(G, G'\) egyszerű gráfok, akkor:

\[ G \cong G' \iff \exists f: V(G) \to V(G') \text{ bijektív fc.}, \text{ amely szomszédságtartó} \]

(azaz \(v, w\) szomszédos \(G\)-ben \(\iff f(v), f(w)\) szomszédos \(G'\)-ben).

Definíció — séta

Legyen \(G = (V, E, \varphi)\) gráf. Ebben a \((v_0, e_1, v_1, e_2, v_2, \dots, v_{l-1}, e_l, v_l)\) sorozatot sétának nevezzük, ha \(v_i \in V\), \(e_i \in E\), és \(\varphi(e_i) = \{v_{i-1}, v_i\}\) (\(i = 1, \dots, l\)).

• A fenti séta nyílt, ha a kiinduló csúcs nem egyenlő az érkezővel (\(v_0 \neq v_l\)).
• A séta zárt, ha \(v_0 = v_l\).
• Egy séta hossza a benne szereplő élek száma (jelölésben: \(l\)).

Definíció — vonal

Egy sétát vonalnak nevezünk, ha nincs benne ismétlődő él (a benne szereplő élek különbözők).

Definíció — út

Egy sétát útnak nevezünk, ha nyílt, és nincs benne sem ismétlődő él, sem ismétlődő csúcs.

Definíció — kör

Egy sétát körnek nevezünk, ha zárt és nincs benne sem ismétlődő él, sem ismétlődő csúcs, kivéve a kezdő és végző csúcs egybeesését.

Definíció — összefüggő gráf

Egy gráf összefüggő, ha minden csúcsából minden más csúcsba vezet út.

Tétel

Egy gráf összefüggő \(\iff\) ha minden csúcsából minden más csúcsba vezet (nyílt) séta.

Bizonyítás

⟹: triviális, mert minden út séta.

⟸: azt kell belátni, hogy ha két különálló csúcs között vezet séta, akkor út is vezet közöttük.

• Ha a sétában lévő csúcsok és élek különbözők, akkor az egy út.
• Tegyük fel, hogy a sétában van ismétlődő csúcs. Ekkor a csúcs két előfordulása közötti részt elhagyva a sétából, rövidebb sétát kapunk.
• Tegyük fel, hogy a sétában van ismétlődő él. Ekkor van ismétlődő csúcs is, ezt pedig már vizsgáltuk.
• A rövidítést szükség esetén többször alkalmazzuk. A végesség miatt előbb-utóbb nem lesz a séta rövidíthető. Ekkor nem lesz benne sem ismétlődő csúcs, sem ismétlődő él, azaz út lesz.

Definíció — komponens

Egy \(G\) gráf komponensén olyan összefüggő részgráfját értjük, ami nem bővíthető másik összefüggő részgráffá (maximálisan összefüggő részgráf).

Definíció — csúcsok távolsága

Legyen \(G\) összefüggő gráf. Ekkor a \(v, w \in V(G)\) különböző csúcsok távolsága a \(v\) és \(w\) közötti legrövidebb út hossza. Továbbá \(v\) és \(v\) távolsága \(0\). Jelölés: \(d(v, w)\).

Tétel — távolságfüggvény tulajdonságai

1. \(\forall v, w \in V(G) : d(v, w) \ge 0\) és \(d(v, w) = 0 \iff v = w\)
2. \(\forall v, w \in V(G) : d(v, w) = d(w, v)\) (szimmetria)
3. \(\forall v, w, z \in V(G) : d(v, w) + d(w, z) \ge d(v, z)\) (háromszög-egyenlőtlenség)

Bizonyítás

(1) és (2) triviális. (3):

• 1. eset: ha \(v = w \implies \underbrace{d(v, w)}_{0} + d(w, z) = d(v, z)\).
• 2. eset: ha \(w = z \implies d(v, w) + \underbrace{d(w, z)}_{0} = d(v, z)\).
• 3. eset: ha \(v = z \implies d(v, w) + d(w, z) \ge 0 = d(v, z)\).
• 4. eset: ha \(v, w, z\) különbözők. Ekkor \(v\)-ből \(w\)-be vezet egy \(d(v, w)\) hosszú út, \(w\)-ből \(z\)-be vezet egy \(d(w, z)\) hosszú út. Ezek összefűzésével kapunk egy \(v\)-ből \(z\)-be vezető \(d(v, w) + d(w, z)\) hosszú sétát. Előző bizonyításban láttuk, hogy a séta lerövidíthető úttá. Ekkor \(v\)-ből \(z\)-be vezet egy legfeljebb \(d(v, w) + d(w, z)\) hosszú út. Így a \(v, z\) közötti legrövidebb út hossza \(d(v, z) \le d(v, w) + d(w, z)\).