Conceptes Fonamentals i Tipus de Grafs en Teoria de Grafs

Tipus Fonamentals de Grafs

Grafs Bàsics

• Graf Nul d'ordre n, Nn

  És un graf d’ordre $n$ i mida $0$.

• Graf Trivial

  És el graf $N_1$ (ordre 1).

• Graf Complet d'ordre n, Kn

  És un graf d’ordre $n$ amb totes les arestes possibles.

  • Mida de $K_n = \frac{n(n-1)}{2}$

• Graf Trajecte d'ordre n, Tn = (V, A)

  És un graf d’ordre $n$ i mida $n - 1$ amb conjunt d’arestes $A = \{x_1x_2, x_2x_3, \dots, x_{n-1}x_n\}$.

  • Grau mínim $\delta(T_n) = 1$ i grau màxim $\Delta(T_n) = 2$.

• Graf Cicle d'ordre n, n >= 3, Cn = (V, A)

  És un graf d’ordre $n$ i mida $n$ amb conjunt d’arestes $A = \{x_1x_2, x_2x_3, \dots, x_{n-1}x_n, x_nx_1\}$.

  • Grau mínim i màxim: $\delta(C_n) = \Delta(C_n) = 2$.

• Graf Roda d'ordre n, n >= 4, Wn = (V, A)

  És un graf d’ordre $n$ i mida $2n - 2$ tal que $A = \{x_1x_2, x_2x_3, \dots, x_{n-1}x_1\} \cup \{x_nx_1, x_nx_2, \dots, x_nx_{n-1}\}$.

Grafs Regulars

Siguin $r$ i $s$ enters positius.

• Graf r-regular d'ordre n

  És un graf regular on $r$ és el grau de tots els vèrtexs.

  • El graf complet $K_n$ és un graf $(n - 1)$-regular.
  • El graf cicle $C_n$ és un graf $2$-regular.
  • Si $G = (V, A)$ és un graf $r$-regular: $2|A| = r|V|$.

Graf Bipartit

Un graf $G = (V, A)$ és bipartit si hi ha dos subconjunts no buits $V_1$ i $V_2$ de $V$ tals que $V = V_1 \cup V_2$ i $V_1 \cap V_2 = \emptyset$, i per a tota aresta $uv \in A$ es té que $u \in V_1$ i $v \in V_2$, o viceversa.

Anomenem $V_1$ i $V_2$ les parts estables del graf.

• Propietat: $\sum_{v \in V_1} g(v) = \sum_{v \in V_2} g(v) = |A|$.

Graf Bipartit Complet, Kr,s = (V, A)

És un graf bipartit amb parts estables $V_1$ i $V_2$ tals que $|V_1| = r$ i $|V_2| = s$, i tots els vèrtexs de $V_1$ són adjacents a tots els vèrtexs de $V_2$. És a dir, $A = \{uv \mid u \in V_1, v \in V_2\}$.

• L’ordre de $K_{r,s}$ és $r + s$ i la mida és $rs$.
• El graf $K_{1,s}$ s’anomena graf estrella.

Graf Complementari

Graf Complementari de G, Gc = (Vc, Ac)

És el graf amb conjunt de vèrtexs $V^c = V$ i conjunt d’arestes $A^c = \{uv \mid u, v \in V \text{ i } uv \notin A\}$.

• Ordre de $G^c = \text{Ordre de } G$.
• Mida de $G^c = \frac{n(n-1)}{2} - |A|$.
• $(G^c)^c = G$.
• Sigui $H$ un graf. Aleshores: $G \cong H \iff G^c \cong H^c$.

Camins, Cicles i Connectivitat

Definicions de Recorreguts

• Camí

  Recorregut on tots els vèrtexs són diferents.

• Cicle

  Recorregut tancat de longitud $\ge 3$ amb tots els vèrtexs diferents (llevat del primer i l’últim, que coincideixen per ser tancat).

Connectivitat

Un graf $G = (V, A)$ direm que és connex si per a tot parell de vèrtexs diferents $u$ i $v$ hi ha un $u$-$v$ camí. Altrament, direm que el graf és no connex.

Elements de Tall

Sigui $G = (V, A)$ un graf. Siguin $v \in V$ i $a \in A$.

• $v$ és un vèrtex de tall o vèrtex d’articulació si $G - v$ té més components connexes que $G$.
• $a$ és una aresta pont si $G - a$ té més components connexes que $G$.

Graf 2-connex

Un graf $G$ és 2-connex si és connex, té almenys $3$ vèrtexs i no té vèrtexs de tall.

Grafs Eulerians

Un recorregut d’un graf s’anomena sender si és obert i no repeteix arestes, i s’anomena circuit si és tancat, no trivial i no repeteix arestes.

Sigui $G$ un graf connex. S’anomena:

• Sender eulerià: un sender que passa per totes les arestes de $G$.
• Circuit eulerià: un circuit que passa per totes les arestes de $G$.
• Graf eulerià: $G$ si té un circuit eulerià.

Condició d'Euler

Un graf $G$ és eulerià si, i només si, tots els vèrtexs tenen grau parell.

Grafs Hamiltonians

Sigui $G$ un graf connex. S’anomena:

• Camí hamiltonià: un camí no tancat que passa per tots els vèrtexs de $G$.
• Cicle hamiltonià: un cicle que passa per tots els vèrtexs de $G$.
• Graf hamiltonià: $G$ si té un cicle hamiltonià.

Condicions Necessàries per a Grafs Hamiltonians

Sigui $G = (V, A)$ un graf hamiltonià d’ordre $n$. Aleshores:

1. $g(v) \ge 2$, per a tot $v \in V$.
2. Si $S \subset V$ i $k = |S|$, el graf $G - S$ té com a molt $k$ components connexes.

Condicions Suficients (Teoremes)

• Teorema d'Ore

  $G = (V, A)$ és un graf d’ordre $n \ge 3$ tal que per a tot $u, v \in V$ diferents i no adjacents es té $g(u) + g(v) \ge n$. Aleshores, $G$ és un graf hamiltonià.

• Teorema de Dirac

  $G = (V, A)$ és un graf d’ordre $n \ge 3$ tal que $g(u) \ge n/2$, per a tot $u \in V$. Aleshores, $G$ és hamiltonià.