Grafo teoria

Matematikan, grafo teoria grafoen azterketa da. Grafo teoriak bere oinarriak matematika diskretuan eta matematika aplikatuan ditu. Zenbait arlotako kontzeptuak erabili behar dira: konbinatoria, aljebra, probabilitatea, poligonoen geometria, aritmetika eta tipologia. Gaur egun gero eta nabarmenagoa da informatikaren arloan, konputazio zientzian eta telekomunikazioetan.

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

Grafoak

Artikulu nagusia: «Grafo»

Grafo bat $G=(V,E)$ bikote ordenatu bat da, $V$ erpin (edo nodo) multzoa eta $E$ ertz multzoa izanik; multzo hori $V$ multzoko erpinen bikote ez-ordenatuek osatzen dute. Horrez gain, $\psi :E\rightarrow \{\{x,y\}\mid x,y\in V\;{\textrm {eta}}\;x\neq y\}$ intzidentzia-funtzioak erpin bikoteak ertzekin erlazionatzen ditu. Erpin berberak lotzen dituen bi ertz albokoak edo auzokideak direla esaten da, eta erpin batera iristen den ertzari intzidente esaten zaio.

Erpin kopuruak grafoaren maila zehazten du, eta ertz kopuruak tamaina; erpin baten ertz intzidente kopuruak, aldiz, erpinaren gradua adierazten du. 0 graduko erpina, hortaz, erpin isolatua da. Grafoko erpin guztien graduen batura grafoaren ertz kopuruaren bikoitza da, izan ere, ertz bakoitzak beti bi erpin lotzen ditu. Erpin guztien graduen batura, arrazoi horrexegatik, beti bikoitia da.

Funtsean, grafoa puntu edo erpin bitartez irudikatutako objektu multzo bat da, objektu horien arteko loturak ertzen bidez irudikatzen direlarik. 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.

Grafoak noranzkorik gabeak edo noranzkoak izan daitezke: ertzek norabide jakinik ez badute noranzkorik gabeak dira, eta ertzek norabide jakin bat dutenean, aldiz, noranzkoak. Grafo noranzkoetan, ertzak gezien bitartez irudikatzen dira. Bestalde, grafo haztatuak ertz bakoitzari balio bat (distantzia, denbora...) ezartzen dioten grafoak dira. Grafo bat haztatua ez bada, haztatu gabeko grafoa dela esaten da.

Historia

Pregel ibaiko 7 zubiak.

Leonhard Eulerrek Königsbergeko zazpi zubiei buruz idatzitako eta 1736an argitaratutako papera grafoen teoriaren historiako lehen papertzat hartzen da. Zazpi zubien ebazkizunaren helburua Königsberg (gaur egun Kaliningrado) hiriko Pregel ibai gaineko zubi guztietatik eta behin bakarrik pasatzen den bide bat aurkitzea da. Eulerrek Solutio problematis ad geometriam situs pertinentis lanean eman zion soluzioa ebazkizunari eta grafoen teoriaren lehen ondoriotzat hartzen da.

Lan honek, baita Vandermondek zaldunaren arazoaz idatzitakoak ere, Leibnizek hasitako situs analisiarekin jarraitu zuen. Eulerren formula, poliedro ganbilaren ertz, erpin eta aurpegi kopurua Cauchyk eta L'Huilierrek ikertu eta orokortu zuten, eta topologia bezala ezagutzen den matematikaren adarraren hasiera irudikatzen du.

Eulerren soluzioa argitaratu eta mende bat baino gehiagora, eta Listingek topologiaren kontzeptua aurkezten zuen bitartean, Arthur Cayleyk, kalkulu diferentzialetik sortutako forma analitikoekiko interesak gidatuta, grafiko-klase jakin bat, zuhaitzak, aztertu zituen. Ikerketa horrek ondorio garrantzitsuak izan zituen kimika teorikoan. Erabili zituen teknikak, batez ere, grafikoen zerrendatzeari buruzkoak dira. Cayleyren emaitzetatik eta George Pólya-k 1935 eta 1937 bitartean argitaratutako funtsezko emaitzetatik sortu zen grafikoen teoria enumeratzailea. Horiek De Bruijn-ek orokortu zituen 1959an. Cayleyk zuhaitzei buruzko bere emaitzak konposizio kimikoaren ikerketa garaikideekin lotu zituen. Hala, matematikako ideiak kimikarekin bateratzea izan da teoria grafikoaren terminologia estandarraren parte bihurtu dena.

Zehazki, grafo terminoa James Joseph Sylvesterrek aurkeztu zuen; 1878an, Nature aldizkarian argitaratutako lan batean, aljebra eta molekula diagramen inbariante kuantiko eta kobarianteen arteko analogia bat eginda, zera zioen:

«

«[...] Inbariante eta kobariante oro Keluléren diagrama edo kimikografo baten berdin-berdina den grafo baten bidez adieraz daiteke. [...] Grafoen biderketa geometrikorako, hau da, ezagunak diren grafoen in- edo kobarianteen biderkaduraren grafoak sortzeko arau bat zehazten dut. [...]»

»

Grafo teoriari buruzko lehen testuliburua Dénes Kőnigek idatzi zuen, eta 1936an argitaratu zen. Frank Hararyren beste liburu bat, 1969an argitaratua, mundua gaiari buruzko behin betiko testuliburutzat hartu zen, eta matematikariei, kimikariei, ingeniari elektrikoei eta gizarte-zientzialariei elkar ulertzeko aukera eman zien. Hararyk erregalia guztiak Pólya saria finantzatzeko eman zituen.

Teoriaren problema ospetsu eta pizgarrienetako bat lau koloreen arazoa da: «Egia al da planoan marraztutako edozein maparen eskualdeak lau kolorez koloreztatu ditzakeela, eta aldi berean muga amankomuna duten bi eskualdek kolore ezberdinak izatea?». Ebazkizuna Francis Guthriek aurkeztu zuen 1852an, eta bere lehen erregistro idatzia Augustus De Morganek, urte berean, Hamiltoni zuzendutako gutun batean dago. Froga oker asko proposatu dira, Cayley, Kempe eta beste batzuenak barne. Tait, Heawood, Ramsey eta Hadwigerrek problema ikertu eta orokortu izanak genus arbitrarioa duten gainazaletan txertatutako grafoen kolorazioak ikertzea ekarri zuen. Taiten birformulazioak problema-klase berri bat sortu zuen: faktorizazio-arazoak, Petersenek eta Kőnigek bereziki aztertuak. Ramseyk eta, bereziki, Turánek 1941ean kolorazioei buruz lortutako emaitzei buruz egindako lanak teoriaren beste adar baten jatorria dira: muturreko grafo teoria.

Lau koloreen arazoa konpondu gabe egon zen mende bat baino gehiagoz, 1969an, Heinrich Heeschek arazoa ordenagailuak erabiliz konpontzeko metodo bat argitaratu zuen arte. 1976an, Kenneth Appel eta Wolfgang Hakenek, ordenagailuz lagunduta egindako froga batek Heeschek garatutako deskargu nozioaren funtsezko erabilera egiten du. Frogak 1.936 konfigurazioren ezaugarriak ordenagailu bidez aztertzea zekarren, eta garaian zuen konplexutasunagatik baztertu egin zen. Robertsonek, Seymourrek, Sandersek eta Thomasek froga sinpleago bat lortu zuten hogei urte beranduago, 633 konfigurazio soilik aztertu behar zituena.

1860 eta 1930 bitartean topologiaren garapen autonomoak, Jordan, Kuratowski eta Whitneyren lanen bitartez, grafo teoriari hazten lagundu zion. Teoriaren eta topologiaren garapen komunaren beste faktore garrantzitsu bat aljebra modernoaren tekniken erabileratik zetorren. Erabilera horren lehen adibidea Gustav Kirchhoff fisikariaren lana da: 1845ean bere Kirchhoffen zirkuituen legeak argitaratu zituen zirkuitu elektrikoetan tentsioa eta korrontea kalkulatzeko.

Metodo probabilistikoak grafo teorian erabiltzen hasteak, batez ere Erdős eta Rényiren grafikoen konektibitatearen probabilitate asintotikoaren azterketan, beste adar bat sortu zuen: ausazko grafo teoria, teoria orokorrean ondorio asko eman dituena.

«Grafo» terminoa ingelesezko «graphic notation» expresiotik dator. Termino hori lehen aldiz erabili zuena Edward Frankland izan zen, eta molekula bateko atomoen arteko loturen adierazpen grafikoari egiten zion erreferentzia.

Aplikazioak

Grafoen teoriari esker hainbat problema ebatzi daitezke: zirkuitu sekuentzialaren sintesia, kontadoreak edo zabaltze sistema esate baterako, eta hainbat arloetarako erabiltzen da, adibidez, marrazketa konputazionala, ingeniaritzaren arlo guztietarako.

Grafoak ibilbideak modelatzeko (autobus bateko lineak, adibidez) ere erabiltzen dira. Produkzio kontrolaren problemetan ere erabiltzen da, baita ordenagailuen sareak proiektatzeko.

Grafoek garrantzia dute biologia eta habitataren ikerkuntzarako. Informazio horrekin, zientzialariek animaliak beren habitatetan nola aldatzen diren uler dezakete.

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

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 beretik, 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_n grafo osoa izanik n ertzekin, K_n,p grafo 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 koloreztatzen 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 propioen kopurua adierazten duena. λ 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|>0 izanik, orduan, koefizienteen 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 problema famoso bat hauxe da: Zenbat kolore beharko dira mapa politiko bat marrazteko, jakinda ondoan dauden bi herrialdek kolore berdina ezin dutela izan? Suposatzen da herrialdeak zati bakarrekoak direla, eta mundua borobila edo planoa dela. Toroide formako mundu batean, hurrengo teoremak ez du balio.

Mapa bat koloreztatzeko, lau kolorerekin 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 iristen garenean laugarren kolore bat sartu beharra dago bai ala bai. Berdina gertatzen da i herrialdearen kasuan.

Ez du inporta herrialdearen formak, nahikoa da jakitea zein herrialde auzokide duen bakoitzak. Grafo batean, herrialdeak erpinak izango lirateke, eta ertz bakoitzak auzokide diren bi erpin edo herrialde elkartuko lituzke. Beraz erpin bakoitzak bere auzokide diren erpinekiko kolore desberdina eduki behar du.

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 denik.

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 $\mathbb {K}$, $\mathbb {K} _{n}$ n -erpineko grafoa izanik.

$\mathbb {K} _{n}$ $n$ erpineko grafo osotu batek ${\frac {n(n-1)}{2}}$ ertz edukiko ditu.

Zatibiko grafoak

Grafo bat G zatibikoa da honela adierazi badaiteke $G=\{V_{1}\cup V_{2},A\}$ ( hots, grafoaren ertzak bi ertz talderen batura da ), baldintza hauek kontuan harturik:

• $V_{1}$ y $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 duenik, 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 ditzakegun.

Grafo isomorfismoa

Bi grafo $G_{1}$ eta $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 gabeko 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 estekak

• Datuak: Q131476
• Multimedia: Graph theory / Q131476