Teorico grafos - Details

Levels:

1) Chapter 1 View

Questions:

34 questions

🇪🇸		🇪🇸

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

Dame las 5 reglas de un polinomio cromatico

1-Coeficientes reales: Los coeficientes del polinomio deben ser números reales. 2-Coeficiente principal: El coeficiente principal del polinomio debe ser 1 (mónico), es decir, el coeficiente de λ^n debe ser 1. 3-No término independiente: El término constante (λ^0) en el polinomio debe ser cero, lo que significa que P(G,0) = 0. 4-Raíces conocidas: Las raíces naturales del polinomio deben ser los números enteros no negativos consecutivos desde 0 hasta el número cromático χ(G) - 1, donde χ(G) es el número cromático del grafo. 5-Coeficiente de menor grado: Si un número natural positivo es raíz del polinomio P(G,λ), entonces debe dividir al coeficiente no nulo de menor grado en el polinomio.

Teorico grafos

Practice Known Questions

Exams

Learn New Questions

Teorico grafos - Leaderboard

Teorico grafos - Details

Levels:

Questions: