|
Artikulu edo pasarte honek eduki, gramatika, hiztegi edota ortografia akatsak ditu.
Lagundu nahi baduzu,
zuzendu ezazu
.
|
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
bikote ordenatu bat da non
erpin ez hutsen multzoa da eta
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
.
Leonhard Eulerrek
Konigsbergeko zazpi zubiei
buruz idatzitako eta 1736an argitaratutako papera grafoen teoriaren historiako lehen papertzat hartzen da
[1]
.
Grafoen teoria
XVIII.mendean
hasten da
Konigsberg-eko zazpi zubietako ebazkizunarekin
, non bilatu behar zen bide bat
Pregel
ibaiko zazpi zubiak pasatzen zituena
Konigsberg
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
1741
ean
, grafoen teoriaren lehen ondorioa kontsideratzen 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
[2]
eta L'Huilierrek
[3]
ikertu eta orokortu zuten, eta
topologia
bezala ezagutzen den matematikaren adarraren hasiera irudikatzen du.
Eulerrek Konigsbergeko zubiei buruz egin zuen paperetik mende bat baino gehiagora, eta
Listingek
topologiaren kontzeptua sartzen zuen bitartean, kalkulu diferentzialetik sortutako forma analitikoekiko interesak gidatu zuen
Cayley
, grafiko-klase jakin bat, zuhaitzak, aztertzeko. Ikerketa honek ondorio asko izan zituen kimika teorikoan
[4]
. Erabili zituen teknikak, batez ere, grafikoen zerrendatzeari buruzkoak dira. Cayleyren emaitzetatik eta Polya-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
[5]
. Matematiketako ideiak kimikakoekin fusionatzea izan zen teoria grafikoaren terminologia estandarraren parte bihurtu dena.
Zehazki,
grafiko
terminoa Sylvesterrek sartu zuen; 1878an Naturan argitaratutako lan batean zioen: analogia bat marrazten duen aljebra eta diagrama molekularren
kuantiko inbaditzaileen
eta
kobarianteen
artean
[6]
:
≪
|
≪[...] Inbariante eta kobariante oro Kekulaan diagrama edo kimikografo baten berdin-berdina den grafiko baten bidez adierazten da. [...] Nik arau bat ematen dut grafikoen biderketa geometrikorako; hau da, grafiko bat eraikitzeko grafiko bananduak ematen zaizkien aldaeren edo kobarianteen biderkadurarako≫
|
≫
|
.
Demografiaren teoriari buruzko lehen testuliburua Denes Knigek idatzi zuen, eta 1936an argitaratu zen
[7]
. Frank Hararyren beste liburu bat, 1969an argitaratua, mundua gaiari buruzko behin betiko testuliburutzat hartu zen
[8]
, eta matematikariei, kimikariei, ingeniari elektrikoei eta gizarte-zientzialariei elkarrekin hitz egiteko aukera eman zien. Hararyk erregalia guztiak eman zituen Polya saria finantzatzeko
[9]
.
Grafikoen teoriaren problema ospetsu eta pizgarrienetako bat lau koloreen arazoa da: ≪Egia al da planoan marraztutako edozein mapak bere eskualdeak lau kolorez koloreztatuak izan ditzakeela muga komuna duen edozein bi eskualdek kolore ezberdinak izan ditzan?≫. Arazo hori Francis Guthriek planteatu zuen 1852an, eta bere lehen erregistro idatzia 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 arazo hori ikertu eta orokortu izanak genero arbitrarioa duten gainazaletan txertatutako grafikoen kolorazioak ikertzea ekarri zuen. Taiten birformulazioak problema-klase berri bat sortu zuen: faktorizazio-arazoak, Petersenek eta Kakigek bereziki aztertuak. Ramseyk eta, bereziki, Turanek kolorazioei buruz 1941ean lortutako emaitzei buruz egindako lanak grafikoen teoriaren beste adar baten jatorrian zeuden, muturreko grafikoen teorian.
Lau koloreen arazoa konpondu gabe egon zen mende bat baino gehiago. 1969an, Heinrich Heeschek arazoa ordenagailuak erabiliz konpontzeko metodo bat argitaratu zuen
[10]
. 1976an, Kenneth Appel eta Wolfgang Hakenek, ordenagailuz lagunduta, egindako froga batek Heeschek garatutako
deskargua
nozioaren funtsezko erabilera egiten du
[11]
[12]
. Froga sinpleago bat, kontuan 633 konfigurazio bakarrik hartzen dituena, hogei urte geroago eman zuten Robertsonek, Seymourrek, Sandersek eta Thomasek
[13]
.
Topologiaren garapen autonomoa 1860 eta 1930eko grafikoen teoria ernaldu zen Jordan, Kuratowski eta Whitneyren lanen bidez. Grafikoen teoriaren eta topologiaren garapen komunaren beste faktore garrantzitsu bat aljebra modernoaren tekniken erabileratik zetorren. Erabilera horren lehen adibidea Gustav Kirchhoff fisikariaren lana da, zeinak 1845ean bere Kirchhoffen zirkuituen legeak argitaratu zituen zirkuitu elektrikoetan tentsioa eta korrontea kalkulatzeko.
Metodo probabilistikoak grafikoen teorian sartzeak, batez ere grafikoen konektibitatearen probabilitate asintotikoaren Erdos eta Renyiren azterketan, beste adar bat sortu zuen, ausazko grafien teoria bezala ezagutzen dena eta emaitza grafiko-teorikoen iturri emankorra izan dena.
≪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
Denes K?nig
argitaratu zuen
1936. urtean
.
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.
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 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 lau
a
: 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.
Hainbat modu daude grafo (sinple) bat errepresentatzeko. Erabilitako datuen estruktura grafoaren ezaugarrien mende eta erabilitako algoritmoa aldatzeko mende daude.
- 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.
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.
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 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
5
-ra edo K
3,3
-ra) bat aurkitzen dugunean.
Topologiarekin
zer ikusia duen arazo bat da grafoak planoak direla ezartzea.
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 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|>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.
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.
Grafo bat arrunta da gehiengoz jota edozein bi erpin ertz batez lotuta badago.
Grafoa arrunta ez bada multigrafoa izendatzen dugu.
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 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
,
n
-erpineko grafoa izanik.
erpineko grafo osotu batek
ertz edukiko ditu.
Grafo bat G zatibikoa da honela adierazi badaiteke
( hots, grafoaren ertzak bi ertz talderen batura da ), baldintza hauek kontuan harturik:
- y
disjuntuak dira eta hutsak.
- A-ko ertz bakoitzak V
1
-eko erpin bat V
2
-eko batekin lotzen du.
- Ez dago ertzik bi elementu lotzen duteik, V
1
; V
2
-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.
Bi grafo
eta
isomorfoak dira bi grafoak grafo beretik lortu badaitezke elementuen banaketa eginez.
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.
Grafo batean
diametroa
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!
- ↑
(Ingelesez)
Graph Theory, 1736?1936.
2021-08-06
(Noiz kontsultatua: 2023-02-09)
.
- ↑
Cauchy, A. L. (1813), "Recherche sur les polyedres - premier memoire",
Journal de l'Ecole Polytechnique
, 9 (Cahier 16): 66?86
- ↑
L'Huillier, S.-A.-J. (1812?1813), "Memoire sur la polyedrometrie",
Annales de Mathematiques
,
3
: 169?189
- ↑
Cayley, Arthur (1821-1895); Cayley, Arthur (1821-1895). (1890).
≪On the theory of the analytical forms called trees≫
IM PAN, call no. 12.807/3
(Noiz kontsultatua: 2023-02-09)
.
- ↑
Cayley, E.. (1875-07-01).
Ueber die analytischen Figuren, welche in der Mathematik Baume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen.
doi
:
10.1002/cber.18750080252
.
(Noiz kontsultatua: 2023-02-09)
.
- ↑
Lockyer, Norman. (1869).
Nature.
[London, etc., Macmillan Journals Ltd., etc.]
(Noiz kontsultatua: 2023-02-09)
.
- ↑
(Ingelesez)
Tutte, W. T.; Tutte, William Thomas. (2001-01-29).
Graph Theory.
Cambridge University Press
ISBN
978-0-521-79489-3
.
(Noiz kontsultatua: 2023-02-09)
.
- ↑
(Ingelesez)
Martin Gardner.
2023-02-07
(Noiz kontsultatua: 2023-02-09)
.
- ↑
(Ingelesez)
Society for Industrial and Applied Mathematics.
2022-10-07
(Noiz kontsultatua: 2023-02-09)
.
- ↑
≪Bibliographisches Institut AG (Mannheim)
v
. VEB Bibliographisches Institut (Leipzig)≫
International Law Reports
72: 26?28. 1987
doi
:
10.1017/cbo9781316152003.008
.
ISSN
0309-0671
.
(Noiz kontsultatua: 2023-02-09)
.
- ↑
Appel, K.; Haken, W.. (1977-09).
≪Every planar map is four colorable. Part I: Discharging≫
Illinois Journal of Mathematics
21 (3): 429?490.
doi
:
10.1215/ijm/1256049011
.
ISSN
0019-2082
.
(Noiz kontsultatua: 2023-02-09)
.
- ↑
Appel, K.; Haken, W.; Koch, J.. (1977-09).
≪Every planar map is four colorable. Part II: Reducibility≫
Illinois Journal of Mathematics
21 (3): 491?567.
doi
:
10.1215/ijm/1256049012
.
ISSN
0019-2082
.
(Noiz kontsultatua: 2023-02-09)
.
- ↑
(Ingelesez)
Robertson, Neil; Sanders, Daniel; Seymour, Paul; Thomas, Robin. (1997-05-01).
≪The Four-Colour Theorem≫
Journal of Combinatorial Theory, Series B
70 (1): 2?44.
doi
:
10.1006/jctb.1997.1750
.
ISSN
0095-8956
.
(Noiz kontsultatua: 2023-02-09)
.
- ↑
Robertson, Neil; Seymour, Paul; Thomas, Robin. (2019-09).
≪Excluded minors in cubic graphs≫
Journal of Combinatorial Theory, Series B
138: 219?285.
doi
:
10.1016/j.jctb.2019.02.002
.
ISSN
0095-8956
.
(Noiz kontsultatua: 2021-10-20)
.