Traseul Hamiltonian (negru)
Graficul grafului Hamiltonian - în teoria graficelor este graficul. care conține un lanț Hamiltonian sau un ciclu Hamiltonian.
Calea Hamiltoniană (sau lanțul Hamiltonian) este o cale (lanț) care conține fiecare vârf al grafului exact o dată. Calea Hamiltoniană, ale cărei noduri inițiale și finale coincid, se numește ciclul Hamiltonian. Ciclul Hamiltonian este un ciclu simplu de spanning (vezi Glosarul teoriei grafurilor).
Calea, ciclul și graficul Hamiltonian sunt numite după matematicianul irlandez W. Hamilton. care a determinat pentru prima dată aceste clase, investigând problema "călătoriei în jurul lumii" pe un dodecaedru. vârfurile nodale ale cărora au simbolizat cele mai mari orașe ale Pământului. iar marginile sunt drumurile de legătură.
Condiții de existență
Condiție necesară
Un grafic nedirecționat G conține un ciclu Hamiltonian atunci când nu există nici un vertex x (i) cu gradul local p (x (i)) în el <2. Доказательство следует из определения.
Starea lui Dirac (în limba engleză) (1952)
Fie p numărul de vârfuri dintr-un grafic dat; Dacă gradul fiecărui vârf nu este mai mic decât, atunci graficul este numit graficul Dirac. Diagrama Dirac este un Hamiltonian.
Starea de rugină (1960)
p este numărul de vârfuri dintr-un grafic dat. Dacă pentru orice pereche de vârfuri neadiacente x, y satisface inegalitatea, atunci graficul este numit un grafic Ore (în cuvinte: gradul de oricare două vârfuri neadiacente este mai mic decât numărul total de noduri din grafic). Graful Ore este un hamiltonian.
Teorema lui Bondy-Khwatal
Teorema lui Bondi-Hwatal (engleză) generalizează declarațiile lui Dirac și Ore. Pentru un grafic G cu vârfuri n, închiderea este determinată prin adăugarea unei margini (u, v) în G pentru fiecare pereche de noduri u și v neadiacente. a cărui sumă de competențe nu este mai mică de n.
Un grafic este Hamiltonian dacă și numai dacă închiderea lui este un grafic Hamiltonian.
Starea Posy
Introducem următoarea funcție f (x) a unui argument integer nonnegative x pe graficul G = [A, B]:
.
Scrisă înseamnă că funcția f (x) în fiecare număr întreg x nenegativ are o valoare egală cu numărul de noduri ale graficului G = [A, B], un grad care nu depășește x. O astfel de funcție f (x) este numită funcția Poisson a graficului G.
Articole similare
Trimiteți-le prietenilor: