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

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

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

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
Avatar utilizator
Mr. Ady
 
Mesaje: 307
Membru din: Mie Dec 08, 2010 10:55 pm
Localitate: Targoviste

Înapoi la Tabara MathTime

Cine este conectat

Utilizatorii ce navighează pe acest forum: Niciun utilizator înregistrat şi 1 vizitator

cron