Erpin (grafo teoria)

Matematikan, grafo teorian, erpina edo nodoa grafoa osatzen duen oinarrizko elementua da: grafoa puntu eta lerro multzo batez osatutako egitura matematikoa da, non lerro bakoitzak bi puntu lotzen dituen; puntuei erpin deitzen zaie eta lerroei ertz. Ertzek norabidea badute, grafo orientatua dugu, eta ez badute, grafo ez-orientatua.

6 erpin eta 7 ertz dituen grafoa.

Erpinak eta graduak

Erpin baten gradua, grafo batean, erpin horri lotutako ertz-kopurua da. Erpin bakartu bat zero graduko erpina da; hau da, ertz intzidenterik ez duen erpina. Erpin hostoa da 1 gradu duen erpina. Grafo zuzendu batean, honakoak bereiz daitezke: irteera-gradua ("outdegree", erpinetik irteten diren ertzen kopurua) eta sarrera-gradua ("indegree", erpinera iristen diren ertzen kopurua); iturburu-erpin bat zero sarrera-gradua duen erpin bat da, eta helburu-erpin bat, berriz, zero irteera-gradua duen erpin bat.

Kanpo estekak
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.