Lovasin arvelu Hamiltonin syklistä

Lovasin arvelu Hamiltonin syklistä on klassinen graafiteorian arvelu.

Se muotoiltiin ohjelmoinnin taiteen neljännessä osassa , mutta todennäköisesti se tunnettiin paljon aikaisemmin.

Sanamuoto

Jokainen äärellinen yhdistetty kärkitransitiivinen graafi sisältää Hamiltonin polun .

Muunnelmia ja yleistyksiä

Mikä tahansa äärellinen yhdistetty kärkitransitiivinen graafi , lukuun ottamatta viittä poikkeusta, sisältää Hamiltonin syklin ; poikkeuksia ovat:
- Täydellinen kaavio , $K_{2}$
- Petersenin graafi ja siitä saatu graafi korvaamalla kukin kärki kolmiolla,
- Coxeterin graafi ja siitä saatu graafi korvaamalla kukin kärki kolmiolla.

Täydellinen kaavio . $K_{2}$
Kreivi Petersen.
Earl of Coxeter.

Yksikään viidestä poikkeuksesta ei ole Earl of Cayley . Tämä havainto johtaa hypoteesin heikompaan versioon

Mikä tahansa äärellisen ryhmän Cayley-graafi sisältää Hamiltonin syklin .

Suunnattujen Cayley-graafien kohdalla olettamus ei pidä paikkaansa.

Erikoistapaukset

Tiedetään, että Abelin ryhmän orientoidulla Cayley-graafilla on Hamiltonin polku.
- Toisaalta sykliset ryhmät, joiden järjestys ei ole alkuluvun potenssi, hyväksyvät suunnatun Cayley-graafin ilman Hamiltonin sykliä. [yksi]
Vuonna 1986 D. Witte osoitti, että olettamus pitää paikkansa p-ryhmien Cayley-graafien kohdalla .
Kysymys jää avoimeksi dihedraalisille ryhmille .

Tiedetään, että symmetriselle ryhmälle olettamus pätee seuraaville generaattorijoukoille:

$a=(1,2,\pisteet ,n),b=(1,2)$ (pitkä sykli ja transponointi ).
$s_{1}=(1,2),s_{2}=(2,3),\dots ,s_{n-1}=(n-1,n)$ ( Coxeter generaattorit ). Tässä tapauksessa Hamiltonin sykli muodostetaan Steinhaus-Johnson-Trotter-algoritmin avulla .
$a=(1,2),b=(1,2)(3,4)\cdots ,c=(2,3)(4,5)\cdots$ .

Linkit

↑ Holsztyński, W. & Strube, RFE (1978), Polut ja piirit äärellisissä ryhmissä , Discrete Mathematics , osa 22 (3): 263–272 , DOI 10.1016/0012-365X(78)90059-6 .