Artikulu hau objektu matematiko buruzkoa da; beste esanahietarako, ikus «Grafo (argipena)».
6 erpin eta 7 ertzeko grafoa.

Grafoa, matematika eta konputazio zientzien ikuspuntutik, objektu multzo bat da, puntu edo erpin bitartez irudikatzen dena, objektu hauek lotzen dituzten lokarri edo ertzekin batera. Grafoak multzoaren elementuen arteko erlazio bitarrak irudikatzea ahalbidetzen du.

DefinizioakAldatu

Grafoa G: = (V,E) formako bikote ordenatua da non:

  • V puntu edo nodo multzo bat den.
  • E lokarri edo ertz multzo bat den.

Normalean finitua izaten da. Grafo askoren emaitza garrantzitsuak ezin dira grafo infinituetan erabili. Grafoaren ordenak puntu edo nodo kopuruak zehazten du.

BegiztakAldatu

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

Grafo ez zuzenduaAldatu

 
Grafo ez zuzendua.

  grafo ez zuzenduak (edo grafo ez-orientatua) ondorengoa betetzen du:

  •  
  •  ,  -ren elementuen ordenatu gabeko bikote multzoa da.

Ordenatu gabeko bikoteak   formako multzoa da, non   den. Multzo hauek 2 kardinaleko  -ren potentzia-multzoarena da, matematikoki   bezala adierazten dena.

Grafo zuzenduaAldatu

 
Grafo zuzendua.

  grafo zuzenduak (edo grafo orientatua) ondorengoa betetzen du:

  •  
  •  ,  -ren elementuen bikote ordenatu multzoa da.

  erpinak emanik, non   hasierako erpina eta   amaierako erpina den.

Definizioz, grafo zuzenduek ezin dute begiztarik eduki.

Grafo bereziakAldatu

Badira ezaugarri bereziak dituzten grafoak. 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 osoa: erpin guztiak konektatuta dituen grafo sinplea, hau da, ertz posible guztiak dituen begiztarik gabeko grafoa.
  • Zatibiko grafoa:   erpin multzoaren   partizioa izanik (bi azpimultzoek ez dute erpin komunik eta bien bildurak   osatzen du), grafoaren ertzak   eta   azpimultzoko erpinekin intzidenteak dira.
  • Zatibiko grafo osoa:   azpimultzoko erpin guztiak   azpimultzoko erpin guztiekin konektatuta dituen zatibiko grafoa.
  • Grafo laua: plano kartesiarrean marraztuz, ertz bat beste batekin gurutzaturik ez duen grafoa.
  • Zuhaitza: ziklo gabeko grafo konektatua.
  • Gurpil grafoa  erpineko zikloari erpin bat gehituz eta azken honetatik zikloko   erpinetara ertz bana konektatuz lortzen den   erpineko grafoa.

Ikus gaineraAldatu

Kanpo estekakAldatu