Eulertar grafo: berrikuspenen arteko aldeak

← Aurreko ezberdintasuna Hurrengo ezberdintasuna →

Ezabatutako edukia Gehitutako edukia

Lerroan

11:46, 8 otsaila 2011ko berrikusketa

Grafo-teorian, grafo eulertarra grafo bateko ertz edo lokarri guztietatik behin bakarrik igarotzen den ibilbidea da. Ibilbidea puntu berean hasi eta bukatzen bada, grafoak zirkuitu eulertarra duela esaten da. Bestela, puntu berean hasi eta bukatzen ez bada alegia, grafoak bide eulertarra duela esaten da. Batzuetan zirkuitu eulertarrik ez baina bai bide eulertarra duten grafoei grafo erdi-eulertar deitu izan zaie.

Grafo eulertar eta erdi-eulertarren existentzia Eulerren teoremaz frogatzen da. Teorema honen arabera, grafo bateko puntu guztietako mailak bikoitiak badira, bada zirkuitu eulertar bat (eta alderantziz, zirkuitu eulertarra badago, puntu guztiak maila bikoitikoak izango dira). Maila bakoitiko puntu kopurua 2 bada, bada ibilbide eulertar bat baina ez zirkuitu eulertarrik (eta alderantziz). Maila bakoitiko puntu kopurua 4 edo handiagoa bada, ez dago ez ibilbide, ez zirkuitu eulertarrik (eta alderantziz). Gogoratu behar da maila bakoitiko puntuen kopurua bikoitia izan behar dela, mailen batura bikoitia izan behar delako. Hau dela eta, maila bakoitiko puntuen kopurua ezin da izan 1, 3, 5, ... izan.

Grafo eulertarren existentziarako Euler-ren teoremak 1736. urtean frogatu zuen Leonhard Euler matematikariak, Königsberg-eko zazpi zubietako ebazkizuna aztertzean.

Propietateak

Ibilbide eta zirkuitu eulertarrak grafoko ertz guztiak zeharkatzen dituzten laburrenak dira, ertz guztiak behin bakarrik zeharkatzen baitituzte.

@@ 1. lerroa: / 1. lerroa: @@
 [[Grafo-teoria]]n, '''grafo eulertarra''' grafo bateko ertz edo lokarri guztietatik behin bakarrik igarotzen den ibilbidea da. Ibilbidea puntu berean hasi eta bukatzen bada, grafoak '''zirkuitu eulertarra''' duela esaten da. Bestela, puntu berean hasi eta bukatzen ez bada alegia, grafoak '''bide eulertarra''' duela esaten da. Batzuetan zirkuitu eulertarrik ez baina bai bide eulertarra duten grafoei '''grafo erdi-eulertar''' deitu izan zaie.
-[[Fitxategi:Labelled_Eulergraph.svg|thumb|Puntu edo erpin guztietako mailak bikoitika dira. Beraz, bada zirkuitu eulertar bat, ertzak alfabeto ordenean jarraituz zeharka daitekeena esaterako.]]
+[[Fitxategi:Labelled_Eulergraph.svg|thumb|Puntu edo erpin guztietako mailak bikoitika dira. Beraz, bada zirkuitu eulertar bat, ertzak alfabeto ordenan jarraituz zeharka daitekeena esaterako.]]
-Grafo eulertar eta erdi-eulertarren existentzia Euler-en teoremaz frogatzen da. Teorema honen arabera, grafo bateko puntu guztietako mailak [[zenbaki bikoiti|bikoitiak]] badira, bada zirkuitu eulertar bat (eta alderantziz, zirkuitu eulertarra badago, puntu guztiak maila bikoitikoak izango dira). Maila bakoitiko puntu kopurua 2 bada, bada ibilbide eulertar bat baina ez zirkuitu eulertarrik (eta alderanntziz). Maila bakoitiko puntu kopurua 4 edo handiagoa bada, ez dago ez ibilbide, ez zirkuitu eulertarrik (eta alderantziz). Gogoratu behar da maila bakoitiko puntuen kopurua bikoitia izan behar dela, mailen batura bikoitia izan behar delako. Hau dela eta, maila bakoitiko puntuen kopurua ezin da izan 1, 3, 5, ... izan.
+Grafo eulertar eta erdi-eulertarren existentzia [[Eulerren teorema]]z frogatzen da. Teorema honen arabera, grafo bateko puntu guztietako mailak [[zenbaki bikoiti|bikoitiak]] badira, bada zirkuitu eulertar bat (eta alderantziz, zirkuitu eulertarra badago, puntu guztiak maila bikoitikoak izango dira). Maila bakoitiko puntu kopurua 2 bada, bada ibilbide eulertar bat baina ez zirkuitu eulertarrik (eta alderantziz). Maila bakoitiko puntu kopurua 4 edo handiagoa bada, ez dago ez ibilbide, ez zirkuitu eulertarrik (eta alderantziz). Gogoratu behar da maila bakoitiko puntuen kopurua bikoitia izan behar dela, mailen batura bikoitia izan behar delako. Hau dela eta, maila bakoitiko puntuen kopurua ezin da izan 1, 3, 5, ... izan.
-Grafo eulertarren existentziarako Euler-en teoremak [[1736]]. urtean frogatu zuen [[Leonhard Euler]] matematikariak, [[Königsberg-eko zazpi zubietako ebazkizun]]a aztertzean.
+Grafo eulertarren existentziarako Euler-ren teoremak [[1736]]. urtean frogatu zuen [[Leonhard Euler]] matematikariak, [[Königsberg-eko zazpi zubietako ebazkizun]]a aztertzean.
 == Propietateak ==