| Que es un grafo no dirigido | Un grafo no dirigido es un tipo de grafo en el cual las aristas representan relaciones simétricas y no tienen un sentido definido. |
| Que es un grafo dirigido | Las aristas tienen un sentido y por tanto no son necesariamente simétricas. |
| Que es un subgrafo | Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. |
| Que es un subgrafo recubridor | Siendo G un grafo el subgrafo recubridor tiene todos los vertices pero no tiene porque tener todas las aristas |
| Que es un subgrafo inducido | Siendo G un grafo y U mi subgrafo inducido, U contiene todas las aristas pero no tiene porque tener todos los vertices de G
Se escribe: <U> |
| Que es un grafo completo | Para todos los vertices existen aristas que conectan todos los vertices
Se escribe Kn siendo en el numero de vertices |
| Que es un grafo complementario | Siendo G un grafo el grafo complenetariop tiene los mismo vertices pero con las aristas que faltan en G
Se escribe /G |
| Que es un grafo bipartito | Dado un grafo G tengo dos grupos de vertices (m y n), todos los vertices de m se conectan con todos los del n.
Se escribe como Km,n |
| Que es el grado de un vertice | Siendo x un vertice el grado de x es la cantidad de aristas que conectan con x
Se escribe gr(x), x es nuestro vertice |
| Escriba el teorema de grados y enuncie el coralario | V=vertice, E=arista y gr(v)=grado del vertice
Σgr(v)=E . 2 y si es regular =v.gr(v)
El coralario explica que la cantidad de vertices de grado impar es par |
| Que es un grafo regular | Un grado es regular si todos los vertices tiene el mismo grado, si gr(v)=k se dice k-regular |
| Que es un camino abierto | Camino que no empieza y termina en el mismo vertice |
| Que es un camino cerrado | Camino que empieza y termina en el mismo vertice |
| Que es un recorrido | Un camino abierto que que no repite aristas |
| Que es un circuito | Un camino cerrado que no repite aristas |
| Que es un camino simple | Un camino abierto que no repite ni aristas ni vertices |
| Que es un ciclo | Un camino cerrado que no repite aristas ni vertices |
| Como contar la cantidad de caminos | Mirando la matriz de adyacencia, la cantidad de caminos en k pasos, entre el vertice i y el vertice j, es el elemento de la posicion(i,j) de la matriz A^k(A matriz de adyacencia) |
| Que es un grafo conexo | Tiene un camino simple para todo par de vertices |
| Que es un grafo no dirigido asociado | Si el grafo no dirigido asociado es conexo entonces el grafo dirigido tambien lo es |
| Que es un grafo disconexo | No conexo, se puede "partir" en partes conexas y la cantidad de divisiones se escribe K(G) |
| Que es un camino euleriano | Un grafo que tiene un camino simple que recorre cada arista solo una vez |
| Que es un circuito euleriano | Un grafo que tiene un ciclo que recorre cada arista solo una vez |
| Cuales son las condiciones circuito euleriano de un grafo no dirigido | -No tiene un vertice aislado
-Es conexo
-El grado de cada vcertice es par |
| Cuales son las condiciones recorrido euleriano de un grafo no dirigido | -No tiene un vertice aislado
-Es conexo
-Solo dos vertices de grado par |
| Que es un camino hamiltoniano | Un camino simple que pasa por todos los vertices solo una vez |
| Que es un circuito hamiltoniano | Un ciclo que pasa por todos los vertices solo una vez |
| Que son los grafos isomorfos | Siendo G y J dos grafos G y F son iguales pero dibujados diferente' |
| Que son los grafos homeomorfos | Dos grafos que si le sacas una arista y un vertice a uno se transofrma en el otro sacrle un vertice y una arista es una division elemental |
| Que es un grafo plano y las regiones | Un grafo las cuales las aristas no se cruzan entre si y las regiones son los espacios generados por esas aristas |
| Que es el grado de una region | Cuantas aristas limtan esa region
La sumatoria de los grados de una region es igual a 2 . E |
| Enuncie los teorema de grafos planos | v =cantidad de vertices
e=cantidad de aristas
r=cantidad de regiones
Se cumple que
v+r-e=2
3r<=2e
e<=3v-6 |
| Enuncie el teorema de kuratoski | Si el grafo contiene un subgrafo que es homeomorfo a k5 o k3,3 no es plano |
