Vecindad (teoría de grafos)

Vecindad (teoría de grafos)
Un grafo de 6 vértices y 7 aristas

En teoría de grafos, un vértice adyacente de un vértice v en un grafo es un vértice que está conectado a v mediante una arista. La vecindad de un vértice v en un grafo G es el subgrafo inducido de G que está formado por todos los vértices adyacentes y todas las aristas que conectan dichos vértices. Por ejemplo, la imagen muestra un grafo de 6 vértices y 7 aristas. El vértice 5 es adyacente a los vértices 1, 2, y 4, pero no es adyacente a los vértices 3 y 6. La vecindad del vértice 5 es el grafo con 3 vértices, 1, 2, y 4, y una arista conectando los vértices 1 y 2.

La vecindad es frecuentemente denotada NG(v) o (cuando el grafo no es ambiguo) N(v). La misma notación también puede referirse a los conjuntos de vértices adyacentes en lugar de al correspondiente subgrafo. La vecindad descrita anteriormente no incluye al mismo v, y es mas específico referirse como la vecindad abierta de v; también es posible definir una vecindad donde v este incluido, llamada la vecindad cerrada y denotada por NG[v]. Cuando aparece sin especificar, la vecindad se presume abierta.


Referencias

  • Hell, Pavol (1978). «Graphs with given neighborhoods I». Colloque internationaux C.N.R.S., No. 260, Problems Combinatories et theorie des graphes. pp. 219–223. 
  • Malnič, Aleksander; Mohar, Bojan (1992). «Generating locally cyclic triangulations of surfaces». Journal of Combinatorial Theory, Series B 56 (2):  pp. 147–164. doi:10.1016/0095-8956(92)90015-P. 
  • Sedlacek, J. (1983). «On local properties of finite graphs». Graph Theory, Lagów. Lecture Notes in Mathematics, no. 1018, Springer-Verlag. pp. 242–247. 
  • Wigderson, Avi (1983). «Improving the performance guarantee for approximate graph coloring». Journal of the ACM 30 (4):  pp. 729–735. doi:10.1145/2157.2158. 

Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Vértice (teoría de grafos) — Para otros usos de este término, véase vértice. Un grafo con 6 vértices y 7 aristas. En teoría de grafos, un vértice o nodo es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está formado por un conjunto de… …   Wikipedia Español

  • Grado (teoría de grafos) — Para otros usos de este término, véase Grado. Un grafo con vértices etiquetados según su grado. El vértice aislado se etiqueta con 0, pues su grado es igual a cero. En Teoría de grafos, el grado o valencia de un vértice es el número de aristas… …   Wikipedia Español

  • Arista (teoría de grafos) — Saltar a navegación, búsqueda Para otros usos de este término, véase Arista (desambiguación). Imagen que muestra representaciones de los distintos tipos de aristas En teoría de grafos las aristas, junto con los vértices, forman …   Wikipedia Español

  • Glosario en teoría de grafos — Anexo:Glosario en teoría de grafos Saltar a navegación, búsqueda Grafo con 6 nodos A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal …   Wikipedia Español

  • Anexo:Glosario de teoría de grafos — Grafo simple no dirigido, con 6 vértices y 7 aristas. A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal correspondiente. Todos los… …   Wikipedia Español

  • Vecindad — puede referirse a: Una vecindad, en teoría de grafos. la condición de vecino; un Vecindario; o el entorno, en topología. Esta página de desambiguación cataloga artículos relacionados con el mismo título. Si llegas …   Wikipedia Español

  • Coeficiente de agrupamiento — Ejemplo de coeficiente de agrupamiento en un [[[grafo no dirigido]] en el que se considera el nodo sombreado on an undirected graph for the shaded node i. Los segmentos de líneas negras son enlaces que conectan vecinos de i, y los segmentos… …   Wikipedia Español

  • Metodología de ciencias sociales — La metodología en las ciencias sociales (como la sociología, antropología, economía y psicología) es el tipo específico de metodología que debe usarse en ciencias sociales con el objetivo de obtener explicaciones veraces de los hechos sociales,… …   Wikipedia Español

  • Sistema de Información Geográfica — En la imagen capas raster y vectoriales en el SIG de código libre QGIS, usado como interfaz gráfica de usuario de GRASS …   Wikipedia Español

  • Vecino (desambiguación) — El término vecino puede referirse a: Vecino, alguien que vive cerca de uno. En teoría de grafos, vecino, un vértice adyacente a otro en un grafo. En topología, entorno, vecino o vecindad. Esta página de desambiguación cataloga artículos relaci …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”