Un grafo G es una pareja G=(V,A), donde V es un conjunto finito (i.e vértices) y A es un subconjunto del conjunto de parejas no ordenadas de V (i.e arcos). Por ejemplo G=({a,b,c},{{a,c},{c,b}}), que se representa gráficamente en la figura 1.1.
Dado un grafo G con V(G) denotamos el conjunto de vértices y con A(G) denotamos el conjunto de arcos. Decimos que un arco {x,y}Î A(G) une los vértices x ey; así que x,y denota el mismo arco que {y,x}. Si {x,y} es un arco, decimos que x e y son extremos del arco, también decimos que x es adyacente o vecino de y.
Un grafo G'=(V',A') es subgrafo de G=(V,A) si V'Ì V y AÌ A'. En tal caso escribimos G'Ì G.
Si G' contiene todos los arcos de G que unen dos vértices de V' decimos que G' es un subgrafo inducido por V' y se denota por G[V'].
El orden de un grafo G es el número de vértices, también se denota por G 1. El tamaño de G es el número de arcos, y se denota por a(G).
Decimos que dos grafos son isomorfos si hay una correspondencia entre sus conjuntos de vértices que preserva la adyacencia. Así que G=(V,E) es isomorfo a G'=(V',E') si hay una biyección j: V V' tal que x,yÎ E si y solo si j(x)j(y)Î E'. Entonces dos grafos isomorfos tienen el mismo orden y el mismo tamaño.
El tamaño de un grafo de orden n es al menos 0 y a lo sumo ( 2n). Un grafo de orden n y tamaño (2n) se llama un n-grafo completo2 y se denota por Kn; un n-grafo vació En tiene orden n y ningún vértice. En todo Kn todo par de vértices son adyacentes, mientras que en En ningún par de vértices son adyacentes.
El conjunto de vértices adyacentes a un vértice xÎ G, se denota por G(x). El grado de x es g(x)= G(x). El grado mínimo de los vértices de un grafo se denota por d(G), mientras que el grado máximo se denota por D(G). Un vértice de grado 0 se dice que es un vértice aislado. Si d(G)=D(G)=k, es decir todo vértice es de grado k entonces se dice que G es k-regular o regular de grado k. Un grafo es regular si es k-regular para algún k.
Dado un grafo G con V(G) denotamos el conjunto de vértices y con A(G) denotamos el conjunto de arcos. Decimos que un arco {x,y}Î A(G) une los vértices x ey; así que x,y denota el mismo arco que {y,x}. Si {x,y} es un arco, decimos que x e y son extremos del arco, también decimos que x es adyacente o vecino de y.
Un grafo G'=(V',A') es subgrafo de G=(V,A) si V'Ì V y AÌ A'. En tal caso escribimos G'Ì G.
Si G' contiene todos los arcos de G que unen dos vértices de V' decimos que G' es un subgrafo inducido por V' y se denota por G[V'].
El orden de un grafo G es el número de vértices, también se denota por G 1. El tamaño de G es el número de arcos, y se denota por a(G).
Decimos que dos grafos son isomorfos si hay una correspondencia entre sus conjuntos de vértices que preserva la adyacencia. Así que G=(V,E) es isomorfo a G'=(V',E') si hay una biyección j: V V' tal que x,yÎ E si y solo si j(x)j(y)Î E'. Entonces dos grafos isomorfos tienen el mismo orden y el mismo tamaño.
El tamaño de un grafo de orden n es al menos 0 y a lo sumo ( 2n). Un grafo de orden n y tamaño (2n) se llama un n-grafo completo2 y se denota por Kn; un n-grafo vació En tiene orden n y ningún vértice. En todo Kn todo par de vértices son adyacentes, mientras que en En ningún par de vértices son adyacentes.
El conjunto de vértices adyacentes a un vértice xÎ G, se denota por G(x). El grado de x es g(x)= G(x). El grado mínimo de los vértices de un grafo se denota por d(G), mientras que el grado máximo se denota por D(G). Un vértice de grado 0 se dice que es un vértice aislado. Si d(G)=D(G)=k, es decir todo vértice es de grado k entonces se dice que G es k-regular o regular de grado k. Un grafo es regular si es k-regular para algún k.
No hay comentarios:
Publicar un comentario