Grafo

Wikipedia, Entziklopedia askea
Hona jauzi: nabigazioa, Bilatu
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.

Definizioak[aldatu | aldatu iturburu kodea]

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.

Begiztak[aldatu | aldatu iturburu kodea]

Begizta bat puntu berdina erlazionatzen duen ertza da.

Grafo ez zuzendua[aldatu | aldatu iturburu kodea]

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 zuzendua[aldatu | aldatu iturburu kodea]

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 bereziak[aldatu | aldatu iturburu kodea]

Badira ezaugarri nabarmenak dituzten grafoak. Hauek dira adibide batzuk:

  • Grafo nulua: erpinik eta ertzik ez duen grafoa. Batzuetan, beharrezkoa izaten da erpin multzoa hutsa ez izatea.
  • Grafo hutsa: ertzik ez duen grafoa.
  • Grafo sinplea: begizta edo ertz paralelorik ez duen grafoa.
  • Multigrafoa: G multigrafoa da baldin eta soilik baldin grafo sinplea ez bada.
  • Grafo osoa: erpin guztiak konektatuta dituen grafo sinplea, hau da, ertz posible guztiak ditu.
  • Zatibiko grafoa: begizta gabeko grafoa, non  erpin multzoaren partizioa den (bi azpimultzoek ez dute erpin komunik eta bien bildurak  osatzen du) eta edozein ertz  eta  azpimultzoekin intzidentea den.
  • Zatibiko grafo osoa: zatibiko grafo bat, non  azpimultzoko erpin guztiak  azpimultzoko erpin guztiekin konektatuta dauden.
  • Grafo laua: plano kartesiarrean marraztuz, ertz bat beste batekin gurutzaturik ez duen grafoa.
  • Zuhaitza: ziklo gabeko grafo konektatua.
  • Gurpil grafoa erpineko grafoa,  erpineko zikloa osatzen duten erpin guztiei  beste erpin bat konektatuz lortzen dena.

Ikus, gainera[aldatu | aldatu iturburu kodea]

Wikimedia Commonsen badira fitxategi gehiago, gai hau dutenak: Grafo Aldatu lotura Wikidatan