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

m
Bot elimina espais sobrants
m (estandarditzant codi encapçalaments i llistes)
m (Bot elimina espais sobrants)
 
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.
 
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|''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 (teoria de grafs)|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.
{{MR|data=2013}}
* {{ref-publicació
| cognom = Gallo
| nom = Giorgio
| cognom2 = Pallotino
| nom2 = Stefano
| article = Shortest path algorithms
| publicació = Annals of Operations Research
| volum = 13 | exemplar = 1 | pàgines = 1–79 | any = 1988
| doi = 10.1007/BF02288320
| ref=harv }}
* 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)
* {{Ref-llibre | cognom=Chartrand | nom=Gary | títol=Introductory graph theory | data=1985 | editorial=Dover | lloc=New York | isbn=0-486-24775-9}}
* {{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}}
* {{Ref-llibre | congom=Harary | nom=Frank | congom2=Palmer | nom2=Edgar M. | títol=Graphical enumeration | data=1973 | editorial=New York, Academic Press | isbn=0-12-324245-2}}
{{Viccionari-lateral|vèrtex}}
 
2.845.982

modificacions