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

Avatar utilizator
Mr. Ady
Mesaje: 307
Membru din: Mie Dec 08, 2010 10:55 pm
Localitate: Targoviste

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

Mesaj de Mr. Ady »

Un graf $G$ este o pereche $G=(V, E)$, unde $V$ - multime de puncte, iar $E$ - o multime de perechi de puncte. $E \subseteq V$ X $V$. Vom identifica o muchie cu cele doua capete ale sale adica scriem o muchie sub forma $(x,y)=(y,x)$ unde $x$ si $y$ sunt varfuri.
Un graf $G$ 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 $2$ puncte.
$2$ varfuri se numesc alaturate daca si numai daca $(x,y) \in E$
Pentru $x \in V$, notam $N(x)$ multimea vecinilor lui $x$. Pentru $x \in V$, notam $d(x)=|N(x)|$ - gradul lui $x$.
Teorema 1: Pentru un graf $G$, $\sum\limits_{v \in V} d(v)=2|E|$.
Demonstratie: La adaugarea unei muchii, fiecare din cele $2$ 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 $x$ 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 $x$ 9aceste varfuri se numesc invecini). Pentru $x \in V$, notam $d^{+}(x)=|N^{+}(x)|$ numit outgradul lui $x$ si $d^{-}(x)=|N^{-}(x)|$ numit ingradul lui $x$.

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 $n$ varfuri $(K_{n)}$
$V(G)$ - multimea varfurilor lui $G$, $E(G)$ - multimea muchiilor lui $G$.
$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 $n$ 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 $n$ 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 ...
Catană Adrian,
Elev la CNIV, Targoviste, clasa a X-a
Scrie răspuns