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.

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 

Grafo teoria