Se spune că un grafic G este conectat. dacă pentru orice pereche de vârfuri diferite ale acestui grafic există un lanț. conectând aceste vârfuri.
Dacă pentru graficul G puteți specifica o pereche de noduri diferite. care nu sunt conectate printr-un lanț (lanț simplu), atunci graficul este denumit deconectat.
Cel mai simplu exemplu al unui grafic deconectat este un grafic care conține un vertex izolat, cel mai simplu exemplu al unui grafic conectat este orice grafic complet Kn.
Teorema graficului de incoerență
Graficul este deconectat dacă și numai dacă mulțimea vârfurilor V poate fi împărțit în două subseturi nevide V1 și V2, astfel încât orice margine grafic conectează nodurile dintr-un subset.
Dovada.
Fie G (V, E) un grafic disjunctiv. Fixați virful v al graficului și notați cu V1 setul. constând din vârful v și toate acele noduri ale V care sunt legate prin lanțuri de vertexul v. Setul V1 nu este gol (conține, dar cel puțin vârf v) și nu coincide cu setul V (cu V1 = V graf G (V, E) - este conectat, între oricare două dintre nodurile sale există diferite lanț care trece prin v). Luați în considerare complementul V2 = V \ V1.
Setul V2 nu este gol și nici o margine a graficului G (V, E) nu conectează orice vârf al V1 cu orice vârf din V2. Prin urmare, seturile construite V1 și V2 formează partiția necesară a setului V.
În schimb, să presupunem că există o partiție V1∪ V2. mulțimea V satisface condiția teoremei.
Să demonstrăm că graficul G (V, E) este deconectat. Luăm o pereche arbitrară de vârfuri v ∈ V1 și w∈ V2. din subseturi diferite și să presupunem că există un lanț care leagă aceste vârfuri. Un astfel de lanț include o margine ale cărei capete aparțin unor subseturi diferite, care contrazic ipoteza. Teorema este dovedită.
Un vârf w al unui grafic este numit realizabil din vârful v dacă fie w = v, fie există un lanț cu începutul v și sfârșitul w.
Corolarul teoremei
Pentru ca graficul G să fie conectat, este necesar și suficient ca în acesta din orice vârf fix să fie accesibile toate celelalte noduri ale acestui grafic.
Proprietățile graficelor
1 ° Fiecare vertex al graficului intră într-o singură componentă conectată.
2 ° Orice grafic finit are un număr finit de componente conectate.
3 ° Este conectat un grafic compus dintr-o singură componentă conectată.
4 ° Fiecare componentă conectată a unui grafic este subgraful său.
5 ° Pentru orice grafic, acesta sau complementul său este conectat.
Dovada proprietăților
Să ne dovedim proprietățile 4 ° și 5 °.
4 °. Fie G1 (V1, E1) o componentă conectată a graficului G (V, E). Considerăm setul de vârfuri V2 = V \ V1 din G care nu aparțin componentei G1 (V1, E1). Dacă îndepărtat din fiecare vârf V2 împreună cu toate muchiile incidente obține subgraf al lui G (V, E) coincide cu G1 component conectat (V1, E1).
5 °. Fie G (V, E) un grafic al ordinului n, iar G = (V, E) complementul lui cu gradația Kn. Când graficul G este conectat, afirmația este evidentă. Fie G un grafic disjunctiv G1 (V1, E1) - unul dintre componentele sale conectate și V2 = V \ V1. Apoi pentru orice noduri v ∈ V1. w ∈ V2 -, în plus, există un vw muchie G ∈ E. Prin urmare, orice nod V2 este conectat la oricare dintre vertex rib V1 aparținând E. și oricare două vârfuri V1 conectate printr-un lanț de lungime 2, ambele legături care se află, de asemenea, în E. Prin urmare, graficul G este conectat.
Articole similare
Trimiteți-le prietenilor: