Grafo teoria

Wikipedia(e)tik
Hona jo: nabigazioa, Bilatu
6 puntu edo erpin eta 7 lokarri edo ertz dituen grafo baten irudia.

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.

Grafoari buruzko oinarrizko kontzeptuak[aldatu | aldatu iturburu kodea]

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.

Grafoen irudikapenak[aldatu | aldatu iturburu kodea]

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.
Commonsen badira fitxategi gehiago, gai hau dutenak: Grafo teoria Aldatu lotura Wikidatan