MathTime

de **Mr. Ady** » Sâm Oct 08, 2011 10:37 pm

Un graf

este o pereche G=(V, E)

, unde

- multime de puncte, iar

- o multime de perechi de puncte. $E \subseteq V$ X

. Vom identifica o muchie cu cele doua capete ale sale adica scriem o muchie sub forma (x,y)=(y,x)

unde

si

sunt varfuri.
Un graf

este simplu daca si numai daca nu contine "bucle" (o muchie de tipul (x, x)

este o bucla).
Un multigraf este un graf in care putem avea mai multe muchii intre

puncte.

varfuri se numesc alaturate daca si numai daca $(x,y) \in E$
Pentru $x \in V$ , notam N(x)

multimea vecinilor lui

. Pentru $x \in V$ , notam d(x)=|N(x)|

- gradul lui

.
Teorema 1: Pentru un graf

, $\sum\limits_{v \in V} d(v)=2|E|$ .
Demonstratie: La adaugarea unei muchii, fiecare din cele

varfuri ale sale "primeste" cate un vecin.

Un graf G pentru care fiecare muchie are o directie se numeste graf directionat.
Pentru un varf $x \in V$ , notam $N^{+}(x)$ multimea varfurilor care nu sunt vecine, din care exista o muchie ce "porneste" din

si ajunge in acel punct (aceste varfuri se numesc outvecini). Pentru $x \in V$ , notam $N^{-}(x)$ ca fiind multimea varfurilor din care porneste o muchie spre

9aceste varfuri se numesc invecini). Pentru $x \in V$ , notam $d^{+}(x)=|N^{+}(x)|$ numit outgradul lui

si $d^{-}(x)=|N^{-}(x)|$ numit ingradul lui

.

Teorema 2: $\sum d^{+}(x)=\sum d^{-}(x)$
Demonstratie: La adaugarea unei muchii, unul dintre varfuri "primeste" un outvecin, iar celalalt un invecin.

Problema: La o intrunire politica, anumiti oameni dau mana. Demonstrati ca numarul de persoane ce au efectuat un numar impari de strangeri de mana este par.
Demonstratie: Se aplica teorema 1.

Exemple de grafuri:
1. Graful complet cu

varfuri $(K_{n)}$
V(G)

- multimea varfurilor lui

,

- multimea muchiilor lui

.
$V(K_{n})=\{1, ..., n\}$ , $E(K_{n})=\{(x,y) | x, y \in \{1, ..., n\}, x<y\}$
$E(K_{n})=C_{n}^{2}$

2. Graful bipartit cu m+n

varfuri $K_{m,n}$
$V(K_{m,n})=\{a_{1}, a_{2}, ..., a_{n}\} \cup \{b_{1}, b_{2}, ..., b_{n}\}$
$E(K_{m,n})=\{(a_{i},b_{j})$ | $i\in \{1,...,n\}, j \in \{1, ..., m\}\}$
$\Rightarrow m \cdot n$ drepte $(E(K_{m,n})=m \cdot n)$

3. Poligonul cu

varfuri $P_{n}$
$V(P_{n})=\{1, 2, ..., n\}$
$E(P_{n})=\{(1,2); ...; (n-1, n);(n,1)\}$

Un drum e o secventa de varfuri $x_{0}, x_{1}, ..., x_{k}$ astfel incat $(x_{0},x_{1}) \in E$ , ..., $(x_{k}, x_{k+1}) \in E$
Un drum simplu este un drum in care orice varf nu se repeta. Lungimea unui drum este numarul de muchii pe care il foloseste.
Un ciclu este un drum, nu neaparat simplu, in care primul si ultimul varf coincid.
Un ciclu simplu este un ciclu in care DOAR primul si ultimul varf coincid.
Lungimea unui ciclu este numarul de muchii pe care il foloseste.
Problema: Intr-o tara avem

orase si unele dintre ele sunt conectate prin zboruri cu sens unic, astfel incat din orice oras, efectuand aceste zboruri, sa nu putem ajunge inapoi. Demonstrati ca se poate completa reteaua de zboruri astfel incat intre oricare 2 orase sa existe un zbor si proprietatea de mai inainte sa fie pastrata.
Lema ajutatoare: Exista $v \in V$ , astfel incat $d^{+}(v)=0$ . Demonstratie: Presupunem contrariul, deci $\forall v \in V$ avem ca $d^{+}(v) \ge 1$ .

Un drum directionat este o secventa $x_{0}, ..., x_{k}$ , astfel incad $(x_{0},x_{1}) \in E$ , ..., $(x_{k-1},x_{k}) \in E$ .
Un ciclu directionat ...

MathTime

Tabara MathTime, ziua I-Teoria Grafurilor-Ömer Cerrahoğlu

Tabara MathTime, ziua I-Teoria Grafurilor-Ömer Cerrahoğlu

Cine este conectat