Grafo-en iturria ikusi

{{argitzeko|objektu matematiko|Grafo (argipena)}}

[[Fitxategi:6n-graf.svg|thumb|250px|6 erpin eta 7 ertzeko grafoa.]]
'''Grafoa''', [[matematika]] eta konputazio zientzien ikuspuntutik, objektu multzo bat da, puntu edo [[Erpin (grafo teoria)|erpin]] bitartez irudikatzen dena, objektu hauek lotzen dituzten lokarri edo [[Ertz (grafo teoria)|ertzekin]] batera. Grafoak multzoaren elementuen arteko erlazio bitarrak irudikatzea ahalbidetzen du.

== Historia eta Königsbergeko zubien arazoa ==
Grafoei buruzko lehen artikulu zientifikoa Leonhard Euler matematikari suitzarrak idatzi zuen 1736an, eta Königsbergeko zubien arazoan oinarritu zen bere artikuluan. Kaliningrad hiria, jatorriz Königsberg, Pregel ibaiaren bi ertzak eta bi uharte lotzen dituzten zazpi zubiengatik zen ezaguna. Bi zubik uharte nagusia ekialdeko ibaiertzarekin lotzen dute, eta beste bik mendebaldekoarekin. Uharte txikia zubi batek lotzen du ertz bakoitzean, eta zazpigarren zubiak bi uharteak lotzen ditu. Arazoa honakoa zen: "Posible al da eskualde horietako edozeinetik hasita, zubi guztietatik igarota eta bakoitza behin bakarrik zeharkatuz abiapuntu berdinera itzultzea?"

Momentuan oinarrizkoa zen grafoen teoriarekin planteatzean, Eulerrek Königsberg-eko zubien eskemari lotutako grafoak konponbiderik ez duela frogatu zuen, hau da, ezin dela abiapuntuko erpinera itzuli ertz batetik bi aldiz pasatu gabe.

Eulerrek arazo orokorra konpondu zuen: zer baldintza bete behar ditu grafo batek, ertz bakoitzetik behin igarota abiapuntuko erpinera itzul daitekeela bermatzeko? Grafo bateko puntu batean dauden lerroen kopurua "gradu" gisa definitzen badugu, orduan erantzuna da zubiak behin zeharkatu daitezkeela baldin eta erpin guztiek gradu bikoitia badute, gehienez bi izan ezik.

== Definizioak ==
'''Grafoa''' ''G: = (V,E)'' formako [[bikote ordenatu]]a da non:
* ''V'' puntu edo nodo multzo bat den.
* ''E'' lokarri edo ertz multzo bat den.

Normalean [[finitu]]a izaten da. Grafo askoren emaitza garrantzitsuak ezin dira [[grafo infinitu]]etan erabili. Grafoaren ordenak puntu edo nodo kopuruak zehazten du.

=== Begiztak ===
Begizta bat puntu berdina erlazionatzen duen ertza da. Besterik esaten ez bada, grafoa begiztarik gabea dela ulertzen da.


Bi ertz edo gehiago paraleloak direla deritzo erpin pare bera erlazionatzen badute.

=== Grafo ez zuzendua ===
[[Fitxategi:Kaari suuntaamaton graafiteoria.png|thumb|Grafo ez zuzendua.]]

<math>G = (V, E)</math> '''grafo ez zuzenduak''' (edo '''grafo ez-orientatua''') ondorengoa betetzen du:
* <math>V\neq\emptyset</math>
* <math>E\subseteq \{x\in\mathcal P(V): |x|=2\}</math>, <math>V\,</math>-ren elementuen ''ordenatu gabeko bikote'' multzoa da.

'''Ordenatu gabeko bikoteak''' <math>\{a, b\}</math> formako multzoa da, non <math>\{a, b\}=\{b, a\}</math> den. Multzo hauek 2 kardinaleko <math>V</math>-ren [[potentzia-multzo]]arena da, matematikoki <math>\mathcal P(V)</math> bezala adierazten dena.

=== Grafo zuzendua ===
[[Fitxategi:Kaari suunnattu graafiteoria.png|thumb|Grafo zuzendua.]]

<math> G = (V, E)</math> '''grafo zuzenduak''' (edo '''grafo orientatua''') ondorengoa betetzen du:
* <math>V\neq\emptyset</math>
* <math>E \subseteq \{(a,b) \in V \times V: a \neq b \}\,</math>, <math>V\,</math>-ren elementuen ''bikote ordenatu'' multzoa da.

<math>(a,b)</math> erpinak emanik, non <math>a</math> ''hasierako erpina'' eta <math>b</math> ''amaierako erpina'' den.

Definizioz, grafo zuzenduek ezin dute ''begiztarik'' eduki.

== Propietateak ==
* '''Auzokidetasuna''': bi ertz auzokideak edo albokoak direla esaten da erpin komun bat badute, eta bi erpin albokoak dira ertz batek elkartzen baditu.
* '''Intzidentzia:''' ertz batek erpin bati eragiten diola deritzogu ertzak beste erpin batekin lotzen badu.
* '''Haztapena:''' ertz bakoitzari balio bat (pisua, luzera, etab.) lotzen dion funtzio bati dagokio, ereduaren adierazkortasuna areagotzeko. Hau asko erabiltzen da optimizazio problemetan.
* '''Etiketatzea:''' Erpinei baita ertzei egiten zaien bereizketa, besteengandik bereizgarri egiten dituen marka baten bidez.

== Adibideak ==
Alboko irudiak honako grafo hau adierazten du:
[[Fitxategi:6n-graf.svg|thumb|6 erpin eta 7 ertzeko grafoa.]]

* ''V'':={1,2,3,4,5,6}
* ''E'':=<nowiki>{{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}</nowiki>

1. erpina 2. erpinaren ondokoa izateagatik, 1 ~ 2  gisa adieraz daiteke.

* ''X'' multzo bateko ''R'' erlazio bitarra grafo zuzendu sinplea da. Bi ertz <math>(a,b) \in X</math> ab izeneko ertz batez lotuta daude baldin eta ''aRb''.

== Grafo bereziak ==
Badira ezaugarri bereziak dituzten [[grafo]]ak. Hona hemen horietako batzuk:
* '''Grafo nulua''': erpinik eta ertzik gabeko grafoa. Batzuetan grafo hutsari grafo nulu esaten zaio.
* '''Grafo hutsa''': ertzik ez baina gutxienez erpin bat baduen grafoa.
* '''Grafo sinplea''': begizta edo ertz paralelorik ez duen grafoa.
* '''Multigrafoa''': sinplea ez den grafoa, hau da, bi erpinen artean ertz bat baino gehiago izatea onartzen duena.
* '''[[Grafo oso]]a''': erpin guztiak konektatuta dituen grafo sinplea, hau da, ertz posible guztiak dituen begiztarik gabeko grafoa.
* '''Zatibiko grafoa''': <math>V</math> erpin multzoaren <math>(W,X)</math> partizioa izanik (bi azpimultzoek ez dute erpin komunik eta bien bildurak <math>V</math> osatzen du), grafoaren ertzak <math>W</math> eta <math>X</math> azpimultzoko erpinekin intzidenteak dira.
* '''Zatibiko grafo osoa''': <math>W</math> azpimultzoko erpin guztiak <math>X</math> azpimultzoko erpin guztiekin konektatuta dituen zatibiko grafoa.
* '''[[Grafo lau]]<nowiki/>a''': plano kartesiarrean marraztuz, ertz bat beste batekin gurutzaturik ez duen grafoa.
* '''Zuhaitza''': ziklo gabeko grafo konektatua.
* '''Gurpil grafoa''': <math>(n-1)</math> erpineko zikloari erpin bat gehituz eta azken honetatik zikloko <math>(n-1)</math> erpinetara ertz bana konektatuz lortzen den <math>n</math> erpineko grafoa.

== Ikus gainera ==

* [[Grafo teoria]]

== Kanpo estekak ==
{{autoritate kontrola}}

[[Kategoria:Grafo teoria]]