Este firesc să ne străduim să reprezentăm structura graficului în cauză cu ajutorul graficelor mai mici și a unei structuri mai simple. Este util să oferim o scurtă notație pentru acele grafice care apar adesea în acest caz. Am introdus deja notația pentru graficul complet Kp și complementul său Kp ', ciclul simplu Cn și lanțul simplu Pn, precum și graful bipartit complet Km, n.
În această secțiune, graficele G1 și G2 au seturi disjuncte de vârfuri V1 și V2 și seturi disjuncte de margini X1 și X2.
Prin combinarea G1ÈG2 a unor astfel de grafice este numit grafic un set de vârfuri, care este V = V1ÈV2. iar setul de margini este X = X1ÈX2
Conectarea grafurilor introduse de Zykov este notată cu G1 + G2, constă în G1ÈG2 și toate marginile care leagă V1 și V2. În special, Km, n = Km + Kn - Aceste operațiuni sunt ilustrate în figură. unde G1 = K2 = P2 și G2 = K1, 2 = P3
Dacă G - conectat grafic, apoi un grafic nG desemnat cu n componente, fiecare dintre acestea fiind izomorf G. Fiecare grafic poate fi scris ca UniGi, unde Gi este diferit de Gj, pentru i! = j. De exemplu, graficul disjunctiv prezentat în figură poate fi scris în formularul 4K1 È ZK2 È 2K3 È K1,2
Există mai multe operații pe graficele G1 și G2, care formează un grafic G cu un set de vârfuri egal cu produsul cartezian V1 X V2. Printre acestea se numără o lucrare (sau un produs cartezian), o compoziție (sau o lucrare lexicografică).
Pentru a defini produsul G1xG2, luați în considerare orice două noduri u = (u1, u2) și v = (v1, v2) de la V = V1 X V2. Nodurile u și v sunt adiacente în G1XG2 dacă și numai dacă [u1 = v1 și u2 adj v2] sau [u2 = v2 și u1 adj u1]. Produsul graficelor G1 = P2 și G2 = P3 este prezentat în figură
Compoziția G = G1 [G2] are de asemenea V = Vi x V2 ca o multitudine de noduri și vârfuri u = (u1, u2) este adiacent la v = (v1, v2) dacă și numai dacă [u1 ASJ v1] sau [u1 = v1 și u2 adj v2]. Pentru graficele G1 și G2 prezentate în figură, două figuri G1 [G2] și G2 [G1], care sunt în mod evident nu izomorfe, sunt arătate în figură
Dacă G1 și G2 - este (p1, q1) - și (p2, q2) -graphs respectiv, este posibil să se găsească numărul de noduri și numărul de muchii din graficul rezultat (vezi tabelul 2.2.) Pentru fiecare dintre operațiile definite mai sus.
numărul de vârfuri numărul de margini
Articole similare
-
Cum este o operație pe hernia intervertebrală, hernia intervertebrală
-
Care a fost numele castelului din basmul copilului cipollino janni
Trimiteți-le prietenilor: