formato traslado unefa
Páginas: 2 (291 palabras)
Publicado: 11 de junio de 2014
Matemáticas Discretas
Guía de ejercicios #2
Prof. Haller Javier Bracho
habracho@gmail.com
Departamento de Matemáticas
Facultad Experimental de Ciencias
Universidad del Zulia
1. Sea
G =(V, E)
un grafo conexo que sea cúbico. Si
|E| = 2|V | − 6,
¾Cuántos vértices y
cuántas aristas tiene el grafo? Dibújelo.
2. Sea
G = (V, E)
un grafo conexo regular con
15aristas. ¾Cuántos vértices puede tener?
Dibuje todas las posibilidades.
3. Si el grafo
Km,12
tiene
72
aristas, ¾Cuánto vale
m
?
4. Dibuje un grafo que sea:
a)
Euleriano yHamiltoniano de
b)
Euleriano y no Hamiltoniano de
6
c)
Hamiltoniano y no Euleriano de
12
d)
Ni Hamiltoniano ni Euleriano de
5. Determinar si existe un grafo con
8vértices.
5
vértices.
15
vértices.
vértices.
vértices cuya sucesion de grados sea
2, 2, 3, 3, 4.
Si
existe, dibújelo.
6. Sea
G = (V, E) un grafo simple con n vértices y q aristas,cuyos vértices tienen grado k
k + 1. Demostrar que si G tiene t vértices de grado k entonces t = (k + 1) · n − 2q
7. Un grafo completo tiene
55
o
aristas. ¾Cuántos vértices tiene?
8.Demostrar que en todo grafo con dos o mas vértices hay dos vértices con el mismo grado.
9. Demostrar que en todo grafo el número de vértices de grado impar es par.
10. Construya un grafo consucesión de grados
11. Si un grafo tiene sucesión de grados
1, 1, 1, 2, 2, 3, 4
1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 5,
1
cuántas aristas tiene?
12. ¾Existe un grafo con sucesión de grados
1,1, 1, 2, 3, 4?
y
1, 1, 1, 1, 1, 2, 3, 4
1, 2, 3, 4?,
y
1, 1, 2, 3, 4?
C5
par
n
y
1, 1, 2, 2, 2, 3, 3.
es isomorfo a su complemento.
15. Si un árbol tiene
16.Suponga que
1, 1, 1, 2, 3, 4?
?
13. Dibuje dos grafos no isomorfos, ambos con sucesión de grados
14. Pruebe que
y
100
vértices, ¾Cuántas aristas tiene?
r es un entero impar....
Guía de ejercicios #2
Prof. Haller Javier Bracho
habracho@gmail.com
Departamento de Matemáticas
Facultad Experimental de Ciencias
Universidad del Zulia
1. Sea
G =(V, E)
un grafo conexo que sea cúbico. Si
|E| = 2|V | − 6,
¾Cuántos vértices y
cuántas aristas tiene el grafo? Dibújelo.
2. Sea
G = (V, E)
un grafo conexo regular con
15aristas. ¾Cuántos vértices puede tener?
Dibuje todas las posibilidades.
3. Si el grafo
Km,12
tiene
72
aristas, ¾Cuánto vale
m
?
4. Dibuje un grafo que sea:
a)
Euleriano yHamiltoniano de
b)
Euleriano y no Hamiltoniano de
6
c)
Hamiltoniano y no Euleriano de
12
d)
Ni Hamiltoniano ni Euleriano de
5. Determinar si existe un grafo con
8vértices.
5
vértices.
15
vértices.
vértices.
vértices cuya sucesion de grados sea
2, 2, 3, 3, 4.
Si
existe, dibújelo.
6. Sea
G = (V, E) un grafo simple con n vértices y q aristas,cuyos vértices tienen grado k
k + 1. Demostrar que si G tiene t vértices de grado k entonces t = (k + 1) · n − 2q
7. Un grafo completo tiene
55
o
aristas. ¾Cuántos vértices tiene?
8.Demostrar que en todo grafo con dos o mas vértices hay dos vértices con el mismo grado.
9. Demostrar que en todo grafo el número de vértices de grado impar es par.
10. Construya un grafo consucesión de grados
11. Si un grafo tiene sucesión de grados
1, 1, 1, 2, 2, 3, 4
1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 5,
1
cuántas aristas tiene?
12. ¾Existe un grafo con sucesión de grados
1,1, 1, 2, 3, 4?
y
1, 1, 1, 1, 1, 2, 3, 4
1, 2, 3, 4?,
y
1, 1, 2, 3, 4?
C5
par
n
y
1, 1, 2, 2, 2, 3, 3.
es isomorfo a su complemento.
15. Si un árbol tiene
16.Suponga que
1, 1, 1, 2, 3, 4?
?
13. Dibuje dos grafos no isomorfos, ambos con sucesión de grados
14. Pruebe que
y
100
vértices, ¾Cuántas aristas tiene?
r es un entero impar....
Leer documento completo
Regístrate para leer el documento completo.