Diferència entre les revisions de "Vèrtiç (teoria de grafo)"
(Pàgina nova, en el contingut: «thumb|Un grafo en 6 vèrtiços i 7 arestes. En teoria d'grafo, un '''vèrtiç''' o '''nodo''' és l'unitat fonamental de la que estan...») |
|||
| Llínea 2: | Llínea 2: | ||
En [[teoria d'grafo]], un '''vèrtiç''' o '''nodo''' és l'unitat fonamental de la que estan formats els [[grafo]]s. Un [[grafo no dirigit]] està format per un conjunt de vèrtiços i un conjunt de [[Aresta (teoria d'grafo)|arestes]] (parells no ordenats de vèrtiços), mentres que un [[grafo dirigit]] està compost per un conjunt de vèrtiços i un conjunt de '''arcs''' ([[parell ordenat|parells ordenats]] de vèrtiços). En este context, els vèrtiços són tractats com a objectes indivisibles i sense propietats, encara que puguen tindre una estructura adicional depenent de l'aplicació per la qual s'usa l'@grafo; per eixemple, una [[ret semàntica]] és un @grafo #a on els vèrtiços representen conceptes o classes d'objectes. | En [[teoria d'grafo]], un '''vèrtiç''' o '''nodo''' és l'unitat fonamental de la que estan formats els [[grafo]]s. Un [[grafo no dirigit]] està format per un conjunt de vèrtiços i un conjunt de [[Aresta (teoria d'grafo)|arestes]] (parells no ordenats de vèrtiços), mentres que un [[grafo dirigit]] està compost per un conjunt de vèrtiços i un conjunt de '''arcs''' ([[parell ordenat|parells ordenats]] de vèrtiços). En este context, els vèrtiços són tractats com a objectes indivisibles i sense propietats, encara que puguen tindre una estructura adicional depenent de l'aplicació per la qual s'usa l'@grafo; per eixemple, una [[ret semàntica]] és un @grafo #a on els vèrtiços representen conceptes o classes d'objectes. | ||
| − | Els dos vèrtiços que conformen una aresta es diuen '''punts finals''' ("endpoints", en anglés), i eixa aresta es diu que és '''incident''' als vèrtiços. Un vèrtiç ''w'' és '''adjacent''' a un atre vèrtiç ''v'' si l'grafo conté una aresta (''v'',''w'') que els unix. La [[Veïnat (teoria d'grafo)|veïnat]] d'un vèrtiç ''v'' és un [[grafo induït]] de l' | + | Els dos vèrtiços que conformen una aresta es diuen '''punts finals''' ("endpoints", en anglés), i eixa aresta es diu que és '''incident''' als vèrtiços. Un vèrtiç ''w'' és '''adjacent''' a un atre vèrtiç ''v'' si l'grafo conté una aresta (''v'',''w'') que els unix. La [[Veïnat (teoria d'grafo)|veïnat]] d'un vèrtiç ''v'' és un [[grafo induït]] de l'grafo, format per tots els vèrtiços adjacents a ''v''. |
== Vèrtiços i graus == | == Vèrtiços i graus == | ||
{{AP|Grau (teoria d'grafo)}} | {{AP|Grau (teoria d'grafo)}} | ||
| − | El [[grau (teoria d'grafo)|grau]] d'un vèrtiç en un | + | El [[grau (teoria d'grafo)|grau]] d'un vèrtiç en un grafo és el número d'arestes incidents a ell. Un '''vèrtiç aïllat''' és un vèrtiç en grau zero; açò és, un vèrtiç que no és punt final de cap aresta. Un '''vèrtiç full''' és un vèrtiç en grau un. En un grafo dirigit, es pot distinguir entre grau d'eixida ("outdegree", número d'arestes que ''ixen'' del vèrtiç) i grau d'entrada ("indegree", número d'arestes que ''apleguen'' al vèrtiç); un '''vèrtiç font''' és un vèrtiç en grau d'entrada zero, mentres que un '''vèrtiç afonat''' és un vèrtiç en grau d'eixida zero. |
== Conexions de vèrtiços == | == Conexions de vèrtiços == | ||
Revisió de 11:16 27 ago 2016
En teoria d'grafo, un vèrtiç o nodo és l'unitat fonamental de la que estan formats els grafos. Un grafo no dirigit està format per un conjunt de vèrtiços i un conjunt de arestes (parells no ordenats de vèrtiços), mentres que un grafo dirigit està compost per un conjunt de vèrtiços i un conjunt de arcs (parells ordenats de vèrtiços). En este context, els vèrtiços són tractats com a objectes indivisibles i sense propietats, encara que puguen tindre una estructura adicional depenent de l'aplicació per la qual s'usa l'@grafo; per eixemple, una ret semàntica és un @grafo #a on els vèrtiços representen conceptes o classes d'objectes.
Els dos vèrtiços que conformen una aresta es diuen punts finals ("endpoints", en anglés), i eixa aresta es diu que és incident als vèrtiços. Un vèrtiç w és adjacent a un atre vèrtiç v si l'grafo conté una aresta (v,w) que els unix. La veïnat d'un vèrtiç v és un grafo induït de l'grafo, format per tots els vèrtiços adjacents a v.
Vèrtiços i graus
- Artícul principal → Grau (teoria d'grafo).
El grau d'un vèrtiç en un grafo és el número d'arestes incidents a ell. Un vèrtiç aïllat és un vèrtiç en grau zero; açò és, un vèrtiç que no és punt final de cap aresta. Un vèrtiç full és un vèrtiç en grau un. En un grafo dirigit, es pot distinguir entre grau d'eixida ("outdegree", número d'arestes que ixen del vèrtiç) i grau d'entrada ("indegree", número d'arestes que apleguen al vèrtiç); un vèrtiç font és un vèrtiç en grau d'entrada zero, mentres que un vèrtiç afonat és un vèrtiç en grau d'eixida zero.
Conexions de vèrtiços
Un vèrtiç de tall és un vèrtiç que en remoure-ho desconecta a l'grafo restant. Un conjunt independent és un conjunt de vèrtiços tal que cap és adjacent a un atre, i una cobertura de vèrtiços és un conjunt de vèrtiços que inclou els punts finals de cada aresta en un grafo.
Vèrtiços etiquetats
En el context d'enumeració i isomorfisme d'grafo, és important distinguir entre vèrtiços etiquetats i vèrtiços no etiquetats. Els vèrtiços etiquetats són aquells que estan associats en informació extra per mig d'etiquetes, que els fa distinguibles entre sí; dos grafos són isomorfs només si existix una correspondència entre els seus parells de vèrtiços en igual etiqueta. Un vèrtiç no etiquetat és un que pot ser substituït per qualsevol atre vèrtiç basat només en els seus *adyacencias en l'grafo, i no en informació adicional a este.
Veïnat d'un vèrtiç
El veïnat d'un vèrtiç x, denotat com <math>N(x),</math> està donat per tots els vèrtiços adjacents a x.
Vore també
- Est artícul fon creat a partir de la traducció de l'artícul es.wikipedia.org/wiki/Vértice (teoría de grafos) de la Wikipedia en espanyol, baix llicència Creative Commons-BY-SA.