Artikulu honek erreferentziak behar ditu. Hemen erreferentzia egiaztagarriak gehituz lagun dezakezu.

Artikulu edo pasarte honek eduki, gramatika, hiztegi edota ortografia akatsak ditu. Lagundu nahi baduzu, zuzendu ezazu.

6 puntu edo erpin eta 7 lokarri edo ertz dituen grafo baten irudia.

Matematikan, grafo bat objektu multzo bat da, puntu edo erpin bitartez irudikatzen dena, objektu hauek lotzen dituzten lokarri edo ertzekin batera. Praktikan, grafoak errepide sareak, ekoizpen prozesu bateko uneak eta aldiak, pertsonen arteko harremanak eta abar irudikatu eta aztertzeko erabiltzen dira. Helburu praktiko horietarako, grafo teoriaren lagungarri den sare teoria garatzen da. Zentzu hertsian, grafo teoria terminoa grafoa matematika puruaren aztergai gisa hartzen denean erabiltzen da. Normalean, grafo bat G=(V,E)displaystyle G=(V,E) bikote ordenatu bat da non Vdisplaystyle V erpin ez hutsen multzoa da eta Edisplaystyle E ertz multzoa da.

Grafo teoria bere oinarriak matematika diskretuan eta matematika aplikatuan ditu. Teoria bat da non zenbait arlotako kontzeptu behar dira konbinatoria, aljebra, probabilitatea, poligonoen geometria, aritmetika eta tipologia. Gaur egun gero eta nagusitasun handiago izan du informatikaren arloan, konputazio zientzian eta telekomunikazioetan.

Historia |

Pregel en Königsberg ibaiko 7 zubiak.

Grafoen teoria XVIII.mendean hasten da Königsberg-eko zazpi zubietako ebazkizunarekin, non bilatu behar zen bide bat Pregel ibaiko zazpi zubiak pasatzen zituena Königsberg hirian, gaur egun Kaliningrado, hortaz, zubi guztiak pasatu behar ziren behin bakarrik pasatzen zubi bakoitzatik. Arazoari buruzko Leonhard Euler-en lana Solutio problematis ad geometriam situs pertinentis 1741ean, grafoen teoriaren lehen ondorioa kontsideratzen da.

Ondoren, 1847ean, Gustav Kirchhoff grafoen teoria erabili zuen sare elektrikoaren analisirako argitaratzen bere zirkuituaren legeak testioa eta korrontea kalkulatzeko zirkuitu elektrikoetan (Kirchhoffen legeak).

1852ean, Francis Guthrie lau koloreen teorema planteatu zuen non bakarrik lau kolore erabiliz marraztu mapa politiko bat non ondoz ondoko bi herrialde ez zuten inoiz kolore berdina izango posible zela baieztatu zuen.

1857ean, Arthur Cayley ikasi eta ebatzi zuen isomeroen enumerazioaren problema, konposatu kimikoak konposisio berdinarekin baina geometria molekurar desberdinarekin.

«Grafo» terminoa H«graphic notation» expresiotik etortzen da, termino hau lehen aldiz erabili zuena Edward Frankland erabili zuen. Eta molekula bateko atomoen arteko loturaren errepresentazio grafikoa egiten zuen erreferentzia.

Grafoen teoriari buruzko lehen libura Dénes Kőnig argitaratu zuen 1936. urtean.

Aplikazioak |

Grafoen teoriari eskez, hainbat problema ebatzi daiteke, adibidez, zirkuitu sekuentzialaren sintesia, kontadoreak edo zabaltze sistema. Hainbat arloetarako erabiltzen da, adibidez, marrazketa konputazionala, ingenieritzaren arlo guztietarako.

Grafoak ere erabili dira ibilbideak modelatzeko. Adibidez, autobus bateko lineak.

Produkzio kontrolaren problemetan erabiltzen da, eta ordenagailuen sareak proiektatzeko.

Grafoak inportanteak dira biologia eta habitatren ikerkuntzarako. Informazio honekin, zientifikoak ulertu dezakete nola aldatu daiteke animaliak beraien habitatetan.

Gaur egun, oso ondo ikus dezakegu grafoak sare sozialetan, hau oso garrantzitsua da datuak ondo pilatzeko.

Grafoari buruzko oinarrizko kontzeptuak |

Grafoa, ohizko zentzuan, G: = (V,E) bikote ordenatu bat da, V puntu edo nodo multzo bat, eta E lokarri edo ertz' multzo bat, V multzoko erpin, puntu edo nodoak lotzen dituztenak, izanik. Erpin kopuruari grafoaren maila deritzo. Ertz kopuruari graforen tamaina deritzo. Bi erpin ertz batez lotuta badaude, ondokoak direla esaten da. Puntu jakin batera heltzen den ertz bati intzidentea dela esaten da.

Erpin bateko ertz intzidenteen erpinaren maila deritzo. Grafoko erpin guztien mailen batura grafoaren tamaina bider bi da, ertz bakoitzak 2 maila ematen baititu. Horregatik ere, erpin guztien mailen batura beti bikoitia da.

Grafoak noranzkorik gabeak, ertzek norabide jakin bat erakusten ez dutenean, eta noranzkoak, ertzek norabide jakin bat dutenean, izan daitezke. Grafo noranzkoetan, ertzak gezien bitartez irudikatzen dira.

Grafo haztatuak ertz bakoitzari balio bat (distantzia bat, denbora bat, ...) ezartzen dioten grafoak dira. Grafo bat haztatua ez bada, haztatu gabeko grafoa dela esaten da.

Grafo motak |

• 
  Grafo sinplea: bi erpinen artean ertz bakarra izan dezakeen grafoa.


• 
  Multigrafoa: bi erpinen artean ertz bat baino gehiago eduki dezakeen grafoa. Grafo sinplea grafo mota honen azpiklasea da.


• 
  Pseudografoa: begizta bat edo gehiago duen grafoa.


• 
  Grafo orientatuta: ertz guztiek orientazio bat dutenean, gezi baten bidez grafikoki.


• 
  Ausazko grafoa: grafo baten ertzak probabilitate batekin erlazionatuta daudenean.


• 
  Hipergrafoa: grafo baten ertzek hiru erpin intzidente edo gehiago dituztenean.


• 
  Grafo laua: plano kartesiarrean marraztuz, ertz bat beste batekin gurutzaturik ez duen grafoa. Kuratowskiren Teoremari esker jakin dezakegu grafo bat laua den edo ez.


• 
  Grafo erregularra: grafo baten erpin guztiek gradu bera dutenean.

Grafoen errepresentazioa |

Hainbat modu daude grafo (sinple) bat errepresentatzeko. Erabilitako datuen estruktura grafoaren ezaugarrien mende eta erabilitako algoritmoa aldatzeko mende daude.

Lista estruktura |

• 
  Eragindako lista - Ertzak errepresentatuta daude bektore bikoiti batekin, non bikoiti bakoitza ertz bat errepresentatzen du.


• 
  Auzokidetasun lista - Erpin bakoitzak erpin lista bat dute non auzokidetasunak dira.


• 
  Graduen lista - zenbaki sekuentzia bat da, non grafoaren erpinen graduekin bat etortzen dira.

Grafoen irudikapenak |

Grafo bat irudi batez azal daiteke, baina grafo bat definitzeko beste era asko daude:

• 
  Intzidentzia zerrenda, non ertz ezberdinek lotzen dituzten erpinen zerrenda egiten den.


• 
  Ondokotasun matrizea, non nxn matrize bat osatzen den, n izanik puntu edo erpin kopurua. Bi puntu ertz batez lotzen badira, 1 ezartzen da, loturik ez badaude, 0 ezartzen da. Grafoa haztatua denean, 0, 1 elementuen ordez, ertzaren balioa (distantzia, denbora, ...) ezartzen da.

Grafoen teoremaren arazoak |

Zikloak eta bide hamiltondarrak |

Ziklo hamiltondiar baten adibidea.

Ziklo bat, ertz auzokideen suzesio bat da, non ez dan pasatzen bi aldiz ertz berdinatik, eta hasierako puntura bueltatzen den. Gainera, ziklo hamiltondiarrak, erpin guztiak pasa behar ditu behin bakarrik (hasierako erpina ezik, hemen bukatuko baitu).

Adibidez, museo handi batean (Louvre-ren antzekoa), hoberena gela guztietatik behin bakarrik pasatzea izango zen, hau da, museoa irudikatzen duen ziklo hamiltondiarra bilatzea (erpinak gelak izango lirateke, eta ertzak, bidea edo gelen arteko ateak).

Bide hamiltondiarra ere dela esango dugu, hasiera puntura bueltatu behar ez denean, sarrerarako ate bakarra duen museo baten antzera. Adibidez, xakeko taula batean zaldi bat lauki guztietatik pasa daiteke lauki berdina bi aldiz zapaldu gabe, hau da, bide hamiltondiar bat da.

Gaur egun ez dira ezagutzen denbora polinomikoan ziklo hamiltondiarrak aurkitzeko modurik, bilaketak oso neketsuak bilakatuz. Hala ere, grafo txikietan zikloak edo ziklo hamiltondiarrak ez direla ziurtatzeko metodoak.

Zihurtatzeko ziklo hamiltondiarren existentziaren arazoa, NP-osoekin konjuntuan sartzen da.

Grafo planoak |

Grafo edo multigrafo bat plano batean bi segmentu beraien artean mozten ez direla marraztea dagoenean, plano bat dela esaten da.

Joko ezagun bat hau izango litzateke: hiru etxe eta hiru putzu marrazten dira. Etxeetako bizilagun guztiak putzu guztiak erabiltzeko eskubidea dute. Gaizki eramaten direnez, ez dute elkarrekin gurutzatu nahi. Posiblea da bederatzi bideak marraztea, bi bide elkarren artean gurutzatu gabe?

Berdin du putzuak eta etxeak nola dauden ipinita, gutxienez beti gurutzaketa bate gongo da.
K_ngrafo osoa izanik n ertzekin, K_n,pgrafo zatibia da n eta p ertzak.

Aurreko jokoarekin ikus daiteke grafo zatibi osoa K_3,3 planoa dela, hau da, gurutzaketarik gabe marraztu dagoenean plano batean, erantzuna ezetz izanik. Normalean, ikus daiteke grafo bat ez dela planoa, bere diseinuan egitura analoga (K₅-ra edo K_3,3-ra) bat aurkitzen dugunean.

Topologiarekin zer ikusia duen arazo bat da grafoak planoak direla ezartzea.

Grafoen kolorazioa |

G=(V, E) grafo ez bideratua bada, G-ren kolorazio propio bat gertatzen da, G-ren erpinak kororeztatzen ditugunean modu honetan, a, b ertz bat da eta orduan G-n a eta b kolore desberdinak dituzte. G-ren kolorazio propioa egiteko behar ditugun kolore kopurua, G-ren zenbaki kromatikoa da, eta C (G) idazten da. Nahiz eta, G grafo ez bideratua izanik, nahiz eta λ kolore kopurua izanik G-ren erpinarako kolorazio propioa. Gure helburua P(G, λ) funtzio polinomial bat bilatzea da, λ aldagaian, G-ren polinomio kromatikoa izena duena, G-ren erpinen kolorazio propien kopurua adierazten dueña. λ kolore kopurua erabiliz.

Polinomio kromatikoen deskonposizioa. G=(V, E) grafo konexoa bada eta e E-ko partaidea bada, orduan: P(G, λ)=P(G+e, λ)+P(G/e, λ), non G/e den ertzen kontrakzioaren bitartez lortzen den grafoa.

Edozein G grafoarentzat, P(G, λ)-n termino konstantea 0 da.

G=(V,E) |E|>0rekin izanik, orduan, koefizienten gehiketa P(G, λ)-n 0 da.

G=(V,E), a,b V ertzen multzoaren partaideak izanik, baina a,b=e, E ertzen multzoaren partaideak ez izanik. G+e idazten dugu G-tik lortzen den grafoa, e=a.b ertza gehitzean. A eta b erpinak G-n adieraztean, G++e G.0000-tik subgrafoa lortzen dugu.

Lau koloreen teorema |

Mapa lau koloretan koloreztatua.

Beste arazo famoso relatibo bat hauxe da: Zenbat kolore beharko dira mapa politiko bat marrazteko, jakinda ondoan dauden bi herrialde kolore berdina ezin dutela izan? Suposatzen da herrialdeak bakarrik puxka batekoak direla, eta mundua borobila edo planoa dela. Toroide formako mundu batean, hurrengo teoremak ez du balio.

Mapa bat koloreztatzeko, lau kolorekin nahikoa da.

Hurrengo mapak erakusten du nola hiru kolore ez diren nahikoak: a herrialde zentraletik hasten bada, eta ahal diren kolore gutxien erabiltzen saiatzen bagara, orduan herrialde horren inguruan dauden herrialdeak kolorez aldatu behar dute. h herrialdera hiristen garenean laugarren kolore bat sartu beharra dago bai ala bai. Berdina gertatzen da i herrialdearen kasuan.

Ez du importa herrialdearen forma, soilik jakitea zein herrialde ikutzen du bakoitzak. Grafo batean, herrialdeak erpinak izango lirateke, eta ertzak batera daudenak juntatzen dituena. Beraz erpin bakoitza kolore desberdina dauka bere ondokoekin konparatuz.

Grafoen karakterizazioa |

Grafo arrunta |

Grafo bat arrunta da gehiengoz jota edozein bi erpin ertz batez lotuta badago.

Grafoa arrunta ez bada multigrafoa izendatzen dugu.

Grafo lotuak |

Grafo bat lotua da erpin bikote bakoitza bide batez lotua badago; hots, edozein bi erpinetarako (a, b), existitzen da a -tik b -ra doan bide bat.

Grafo bat lotura bikoitzekoa da baldin eta erpin bikote bat bi bide disjuntuetatik lotu badaitezke; hau da, grafo lotua da eta ez dago erpinik grafotik kendu eta azpigrafo hori askea ddenik.

Grafo lotua eta ez lotua edo askea.

Grafo osotuak |

Grafo bat osotua da baldin eta existitzen badira erpin bikote posible guztiak lotzen dituen ertzak; hau da, edozein erpin bikotek (a, b) elkarrekin lotzen dituen e ertz bat behar du.

Grafo osotuen multzoa honela adierazten da Kdisplaystyle mathbb K , Kndisplaystyle mathbb K _n n -erpineko grafoa izanik.

Kndisplaystyle mathbb K _n ndisplaystyle n erpineko grafo osotu batek n(n−1)2displaystyle frac n(n-1)2 ertz edukiko ditu.

Zatibiko grafoak |

Grafo bat G zatibikoa da honela adierazi badaiteke G=V1∪V2,Adisplaystyle G=V_1cup V_2,A ( hots, grafoaren ertzak bi ertz talderen batura da ), baldintza hauek kontuan harturik:

• 
  V1displaystyle V_1 y V2displaystyle V_2 disjuntuak dira eta hutsak.


• A-ko ertz bakoitzak V₁-eko erpin bat V₂-eko batekin lotzen du.


• Ez dago ertzik bi elementu lotzen duteik, V₁; V₂-n ere ez.

Baldintza hauek betetzen dituen grafoa zatibikoa da. Informalki, bi elementu desberdinen multzoak lotzen dituen grafo bezala definitu dezakegu. Adibidez, puzzle bateko piezak, non lehen zutabeko elementuak bigarren zutabeko elementuekin erlaziona ditzazkegun.

Grafo isomorfismoa |

Bi grafo G1displaystyle G_1 eta G2displaystyle G_2 isomorfoak dira bi grafoak grafo beretik lortu badaitezke elementuen banaketa eginez.

Zuhaitzak |

Zuhaitzaren adibidea.

Ziklorik gabeko eta punto guztiekin konektatzen duen grafoari zuhaitz deitzen zaio. n erpineko grafo batean, zuhaitzek n - 1 erpin dituzte zehazki eta n^n-2 zuhaitz posible daude. Zuhaitzen garrantzia ahalik eta ertz gutxiekin, ahalik eta erpin gehienak konektatzean datza.

Diametroa |

K₄ planoa dela ikusi dezakegu, aldiz, K₅ ez, eta berriz K₃,₂ bai.

Grafo batean diámetroa bi erpinen arteko ertz gutxieneko loturaren distantzia da.

K_n grafoen diametroa 1 da, K_n,_p grafoena berriz, 2. DIametro infinitua duen grafo bat infinitu erpin dituela esan nahi du edo besterik gabe, ez dela lotua.

Internetaren munduak modan jarri du diametroaren ideia: estekarik gameko web-orriak kentzen baditugu eta bi web-orri zoriz aukeratu, zenbat klik behar ditugu web-orri batetik bestera heltzeko? Emaitza izan ere Internet-aren diametroa da, non web-orriak erpinak diren eta ertzak sareko estekak.

Bizitza errealean ere analogia bat dago: zoriz aukeratutako munduko bi pertsona, zenbat jauzi behar dira batetik bestera heltzeko, jauzia bi pertsona ezagunen artean gertatu behar baldin bada? Definizio hau kontuan harturik, jo dezakegu gizakiaren diametroa... Zortzi besterik ez dela!

Kanpo loturak |

Wikimedia Commonsen badira fitxategi gehiago, gai hau dutenak: Grafo teoria

• 
  Grafo-teoria, Gizapedian.