Scribd
Cargar
305 vistas1 página

Formulario - Grafos

Este documento presenta definiciones y teoremas fundamentales sobre grafos. Introduce conceptos como grado de un vértice, operaciones con grafos como complemento, y familias comunes de grafos como ciclos, ruedas y bipartitos. Explica propiedades de recorridos, distancias e isomorfismos en grafos. Finalmente, se enfoca en árboles definiéndolos y presentando teoremas sobre sus propiedades como que un grafo es un árbol si y solo si el número de aristas es igual al número de vértices menos uno

Cargado por

Wilmer Villca Maron
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
305 vistas1 página

Formulario - Grafos

Este documento presenta definiciones y teoremas fundamentales sobre grafos. Introduce conceptos como grado de un vértice, operaciones con grafos como complemento, y familias comunes de grafos como ciclos, ruedas y bipartitos. Explica propiedades de recorridos, distancias e isomorfismos en grafos. Finalmente, se enfoca en árboles definiéndolos y presentando teoremas sobre sus propiedades como que un grafo es un árbol si y solo si el número de aristas es igual al número de vértices menos uno

Cargado por

Wilmer Villca Maron
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
Está en la página 1/ 1

CAPÍTULO 1 Vértice central: si su excentricidad es mínima: sí e(v) = rad(G).

Conceptos fundamentales Teorema 2.3 Para cualquier grafo G conexo y no trivial se cumple:

Grado o valencia d(v), de un vértice v en una grafo G, es el número de rad(G) ≤ diam(G) ≤ 2rad(G)
aristas que concurren en v.
Teorema 2.4 Sean G y H grafos. Si G contiene un k-ciclo, pero H no,
0 ≤ δ(G) ≤ d(v) ≤ Δ(G) ≤ n – 1 entonces G no es isomorfo con H.

Teorema 1.1 (Primer teorema de la Teoría de Grafos) Si G es un grafo de Teorema 2.5 Si G y H son isomorfos, entonces los grados de los vértices de
tamaño m, entonces G son los mismos que los grados de los vértices de H.
❑
∑ d ( v ) =2 m
v ∈V (G)
CAPÍTULO 3
Teorema 1.2 En un grafo cualquiera, el número de vértices de grado impar Árboles
es par.
Definición.- Sea e una arista de un grafo G. Si G – e tiene más componentes
Teorema 1.3 Si n ≥ 2, no existe un grafo G de orden n cuyos vértices sean que G, entonces la arista e se denomina un puente de G.
todos de distinto grado.
Teorema 3.1 Sea e una arista del grafo G, e es un puente si y sólo si e no
Familias comunes de grafos está en ningún ciclo de G.
Trayectorias, es un grafo Tk no vacío (V, A) tal que: Definición.- Un grafo conexo y sin ciclos se llama árbol.
V = {v0, v1, v2, . . . , vk} Teorema 3.2
Donde todos los vi son distintos. La longitud de una trayectoria es el número a) Todo subgrafo conexo de un árbol, es un grafo.
de aristas. b) Todo árbol no trivial tiene al menos dos hojas.
Ciclos, el grafo Ck = Tk – 1 + vk – 1v0 se denomina un ciclo. NOTA 1. Si u es una hoja de un árbol T, entonces T – u es un árbol.
Grafos rueda se obtiene a partir del ciclo Ck – 1, k ≥ 4, uniendo con una arista NOTA 2. Si T es un árbol y le añadimos una hoja (con su arista
cada uno de sus vértices con un nuevo vértice v, es el grafo rueda de k correspondiente) el nuevo grafo es también un árbol.
vértices denotado Wk.
Teorema 3.3 Sea T un grafo conexo de orden n y tamaño m. T es un árbol si
Grafo completo es un grafo en el cual cada par de vértices son adyacentes. y sólo si n = m+1.
Un grafo completo de n vértices se denota por Kn.
Teorema 3.4 Un grafo G es un árbol si y sólo si cualesquiera dos vértices de
Grafo regular es un grafo cuyos vértices tienen todos ellos el mismo grado. G están conectados por una única trayectoria.
En un grafo regular de grado r, con n vértices y m aristas, entonces 2m = rn.
Teorema 3.5 Si T = (V, A) es un árbol de orden n y tamaño n entonces:
Grafo bipartido, si sus vértices pueden separarse en dos conjuntos disjuntos ❑
V1 y V2 de modo que toda arista de G tiene un extremo en V1 y el otro
extremo en V2. Lo denotaremos por G(V1, V2).
∑ d ( v ) =2 n−2
v ∈V (G)
Grafo bipartido completo, en este caso si V1 tiene r vértices y V2 tiene s
vértices, lo denotaremos por Kr, s . Corolario 3.6 Sea T un árbol de orden n ≥ 3 con grado máximo Δ y con n i
vértices de grado i (para 1 ≤ i ≤ Δ), entonces el número de hojas de T es
Operaciones con grafos.- dado por:

Complemento G de un grafo G, si toda arista de G no es arista de G. El n1 = 2 + n3 + 2n4 + 3n5 + . . . + (Δ – 2)nΔ


tamaño de G es n(n – 1)/2.
Definición.- Un grafo con ciclos es un bosque.
Teorema 1.4 Para cada par de enteros r y n, no ambos impares, con 0 ≤ r ≤
n-1, existe un grafo r-regular de orden n. Teorema 3.7 El tamaño m de un bosque de orden n y con k componentes es
m = n – k.

Teorema 3.8 Si d1, d2, . . . , dn son n ≥ 2 enteros positivos cuya suma es 2n –


CAPÍTULO 2 2, entonces estos son los grados de los vértices de algún árbol T de orden n.

Recorridos, distancia e isomorfismo

Teorema 2.1 Si un grafo G contiene un camino u – v, entonces contiene una


trayectoria u – v.

Teorema 2.2 Un grafo G es bipartido si y sólo si G no contiene ciclos de


longitud impar.

Excentricidad: e(v) es la distancia de v hasta el vértice más alejado de v.


Esto es:

e(v) = maxxV(G){d(v, x)}

Diámetro: diam(G) es el máximo valor de las excentricidades de vértices de


G o, de modo equivalente, es la máxima distancia entre dos vértices de G.

Radio: rad(G) es el mínimo valor de las excentricidades de los vértices.

También podría gustarte