Vèrtex (teoria de grafs)
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 grafs: un graf no dirigit consisteix en un conjunt de vèrtexs i un conjunt d'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.
Des del punt de vista de la teoria de grafs, els vèrtexs són tractats com objectes indivisibles i sense cap característica, encara que poden tenir una estructura addicional en funció de l'aplicació que motiva el graf.
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 d'un vèrtex v és un subgraf induït del graf, format per tots els vèrtexs adjacents a v.
Tipus
[modifica]El 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.
Un vèrtex de tall és un vèrtex l'eliminació del qual implicaria desconnectar el gràf restant; un separador de dos vèrtexs a i b és un conjunt de vèrtexs l'eliminació dels quals implicaria desconnectar a de b. Un graf k-vèrtex-connectat és un graf en el qual l'eliminació de menys de k vèrtexs sempre deixa el graf connectat. Un conjunt independent és un conjunt de vèrtexs del qual cap parell de vèrtexs no és adjacent, i una coberta de vèrtexs és un conjunt de vèrtexs que inclou el punt final de cada aresta del graf. L'espai de vèrtexs d'un graf és un espai vectorial on els vectors d'una base de l'espai corresponen amb els vèrtexs del graf.
Un graf és vèrtex-transitiu si té simetries que transformen qualsevol vèrtex a qualsevol altre vèrtex. En el context de l'enumeració de grafs i isomorfisme de grafs és important distingir entre vèrtexs etiquetats i vèrtexs no etiquetats. Un vèrtex etiquetat és un vèrtex que està associat a informació addicional que permet que es pugui distingir d'altres vèrtexs etiquetats; dos grafs poden ser isomorfs només si la correspondència entre els seus vèrtexs aparellen vèrtexs amb etiquetes iguals. En canvi, un vèrtex no etiquetat és aquell que pot ser substituït per qualsevol altre vèrtex basant-se només en les seves adjacències en el graf, i no en cap informació addicional.
Els vèrtexs d'un graf són anàlegs a, però no el mateix que, els vèrtexs de poliedres: l'esquelet d'un poliedre forma un graf, els vèrtexs del qual són els vèrtexs del políedre, però els vèrtexs del políedre tenen una estructura addicional (la seva localització geomètrica) que és no es troba en la teoria de grafs. La figura de vèrtex d'un vèrtex d'un poliedre és anàloga al veïnatge d'un vèrtex en un graf.
Vegeu també
[modifica]Referències
[modifica]
 |
Aquest article té bibliografia, però no se sap quina referència verifica cada part. Podeu millorar aquest article assignant cadascuna d'aquestes obres a frases o paràgrafs concrets. |
- Gallo, Giorgio; Pallotino, Stefano «Shortest path algorithms». Annals of Operations Research, 13, 1, 1988, pàg. 1–79. DOI: 10.1007/BF02288320.
- Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)
- Chartrand, Gary. Introductory graph theory. Nova York: Dover, 1985. ISBN 0-486-24775-9.
- Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press, 1986. ISBN 0-19-853916-9.
- Harary, Frank. Graph theory. Reading, Mass.: Addison-Wesley Publishing, 1969. ISBN 0-201-41033-8.
- Graphical enumeration. Nova York, Academic Press, 1973. ISBN 0-12-324245-2.