Vèrtex (teoria de grafs): diferència entre les revisions

En [[matemàtiques]], i més especialment en [[teoria de grafs]], un '''vèrtex''' (plural '''vèrtexs''') o '''node''' és la unitat fonamental de la qual es formen els [[graf|grafs]]: un [[graf no dirigit]] consisteix en un conjunt de vèrtexs i un conjunt d'[[Aresta (teoria de grafs)|arestes]] (parells no ordenats de vèrtexs), mentre que un [[graf dirigit]] consisteix en un conjunt de vèrtexs i un conjunt d'arcs (parells ordenats de vèrtexs). En el diagrama d'un graf, un vèrtex es representa generalment amb un cercle i una etiqueta, i una aresta amb una línia o fletxa que s'estén des d'un vèrtex a un altre.

 

Els dos vèrtexs que formen una aresta es diu que són els seus punts finals o extrems, i l'aresta es diu que és incident als vèrtexs. Un vèrtex ''w'' es diu que és adjacent a un altre vèrtex ''v'' si el graf conté una aresta (''v'',''w''). El [[veïnat (teoria de grafs)|veïnat]] d'un vèrtex ''v'' és un [[subgraf induït]] del graf, format per tots els vèrtexs adjacents a ''v''.

 

El [[grau (teoria de grafs)|grau]] d'un vèrtex en un graf és el nombre d'arestes incidents a ell. Un '''vèrtex aïllat''' és un vèrtex amb grau zero; és a dir, un vèrtex que no és un punt final de cap aresta. Un '''vèrtex fulla''' és un vèrtex amb grau un. En un graf dirigit, es pot distingir el grau de sortida (nombre d'arestes sortints) del grau d'entrada (nombre d'arestes entrants); un '''vèrtex font''' és un vèrtex amb grau d'entrada zero, mentre que un '''vèrtex dissipador''' és un vèrtex amb grau de sortida zero.

 

 

== Vegeu també ==

* [[Glossari de teoria de grafs]]

 

* {{Ref-llibre | cognom=Biggs | nom=Norman | cognom2=Lloyd | nom2=E. H. | cognom3=Wilson | nom3=Robin J. | títol=Graph theory, 1736-1936 | data=1986 | editorial=Clarendon Press | lloc=Oxford [Oxfordshire] | isbn=0-19-853916-9}}

* {{Ref-llibre | cognom=Harary | nom=Frank | títol=Graph theory | data=1969 | editorial=Addison-Wesley Publishing | lloc=Reading, Mass. | isbn=0-201-41033-8}}

 

 

[[Categoria:Teoria de grafs]]