Ore-tétel

• IPA:

Ore-tétel

1. (matematika, gráfelmélet) Az Ore-tétel elégséges feltételt ad gráfban Hamilton-kör létezésére, lényegében azt állítja, hogy elegendően nagy számú éllel rendelkező gráfnak mindig van Hamilton-köre. Specifikusan a tétel a nem szomszédos csúcspárok fokszámainak összegeit vizsgálja: ha bármely nem szomszédos csúcspár fokszámösszege eléri a gráf csúcsainak számát, akkor a gráfnak van Hamilton-köre.

Az **Ore-tétel** a gráfelmélet egyik fontos tétele, amely egy gráf Hamilton-körének létezésére ad elegendő feltételt. A tétel kimondja, hogy ha egy gráf csúcsai között bizonyos fokszámok összege elég nagy, akkor a gráf tartalmaz Hamilton-kört.

Legyen ${\displaystyle G=(V,E)}$ egy ${\displaystyle n}$-csúcsú egyszerű gráf (${\displaystyle n\geq 3}$). Ha bármely két nem szomszédos csúcs fokszámának összege legalább ${\displaystyle n}$, azaz:

$${\displaystyle \deg(u)+\deg(v)\geq n\quad {\text{minden }}u,v\in V{\text{ nem szomszédos csúcsra}},}$$

akkor ${\displaystyle G}$ tartalmaz Hamilton-kört.

---

Tegyük fel, hogy ${\displaystyle G}$ nem tartalmaz Hamilton-kört. Ez ellentmondásra vezet a feltétellel.

---

Legyen ${\displaystyle P}$ a ${\displaystyle G}$ gráfban egy maximális Hamilton-út, amely ${\displaystyle v_{1},v_{2},\dots ,v_{k}}$ csúcsokból áll, ahol ${\displaystyle k\leq n}$. Ez azt jelenti, hogy ${\displaystyle P}$-hez nem adható hozzá további csúcs úgy, hogy az út továbbra is Hamilton-út maradjon.

---

A maximális Hamilton-út ${\displaystyle P}$ tulajdonságaiból következik, hogy:

• A ${\displaystyle P}$ végpontjai (${\displaystyle v_{1}}$ és ${\displaystyle v_{k}}$) nem kapcsolhatók össze, különben ${\displaystyle P}$-ből Hamilton-kört lehetne alkotni, ami ellentmond a feltételezésnek.
• A ${\displaystyle v_{1}}$-gyel nem szomszédos csúcsoknak a ${\displaystyle P}$-n belül létezniük kell, és ugyanez igaz a ${\displaystyle v_{k}}$-ra is.

---

Tekintsük ${\displaystyle v_{1}}$ és ${\displaystyle v_{k}}$ fokszámát. Az Ore-feltétel szerint:

$${\displaystyle \deg(v_{1})+\deg(v_{k})\geq n.}$$

Ez azt jelenti, hogy ${\displaystyle v_{1}}$ és ${\displaystyle v_{k}}$ fokszámainak összege elég nagy ahhoz, hogy legalább ${\displaystyle n}$-nyi csúcsot lefedjenek.

---

Ha ${\displaystyle v_{1}}$-hez vagy ${\displaystyle v_{k}}$-hoz szomszédos csúcsok révén bővítenénk az ${\displaystyle P}$-t, akkor ellentmondásra jutnánk, mert ${\displaystyle P}$ már maximális Hamilton-út, és nem tartalmazhat további csúcsot.

Ezért az Ore-feltétel megsértése nélkül ${\displaystyle P}$-t ki lehetne egészíteni, így Hamilton-kört alkotva. Ez ellentmond az eredeti feltételezésünknek.

---

Mivel az Ore-feltétel teljesül, és ${\displaystyle P}$-ből mindig létrehozható Hamilton-kör, a gráf ${\displaystyle G}$ tartalmaz Hamilton-kört.

---

Az Ore-tétel általánosabb, mint a Dirac-tétel, amely szerint ha egy gráfban minden csúcs fokszáma legalább ${\displaystyle n/2}$, akkor a gráf tartalmaz Hamilton-kört. Az Ore-tétel gyengébb feltételekkel is garantálja Hamilton-kör létezését.

---

Legyen ${\displaystyle G}$ egy 6 csúcsú gráf (${\displaystyle n=6}$), ahol minden nem szomszédos csúcs fokszámának összege legalább 6. Az Ore-tétel alapján ${\displaystyle G}$-nek léteznie kell Hamilton-körnek.

Egy lehetséges gráf például:

• Csúcsok: ${\displaystyle V=\{1,2,3,4,5,6\}}$,
• Élek: ${\displaystyle E=\{(1,2),(2,3),(3,4),(4,5),(5,6),(6,1)\}}$.

---

Az **Ore-tétel** egy elegendő feltételt ad Hamilton-kör létezésére egy gráfban, amely a csúcsok fokszámának összegére épül. A tétel fontos szerepet játszik a gráfelméletben, különösen a Hamilton-körök létezésének vizsgálatában.

• Ore-tétel - Értelmező szótár (MEK)
• Ore-tétel - Etimológiai szótár (UMIL)
• Ore-tétel - Szótár.net (hu-hu)
• Ore-tétel - DeepL (hu-de)
• Ore-tétel - Яндекс (hu-ru)
• Ore-tétel - Google (hu-en)
• Ore-tétel - Helyesírási szótár (MTA)
• Ore-tétel - Wikidata
• Ore-tétel - Wikipédia (magyar)