Vèrtex (teoria de grafs): diferència entre les revisions
Contingut suprimit Contingut afegit
Robot passa data de manteniment de mesos a anys |
m cometes |
||
Línia 11:
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.
Els vèrtexs d'un graf són anàlegs a, però no el mateix que, els [[Vèrtex (geometria)|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.
| |||