Temas Variados

Tarea #7
Fundamentos de Inform´tica II
a
Hang in there!
Horst H. von Brand
Natalia Ruz
Leon´ G´mez
ıas o

Paulina Silva
Pablo Inzunza

Cristian Orellana

22 de marzo de 2012Problemas
1.

Grafos
Considere el grafo representado por la siguiente matriz de adyacencia

A
B
C
D
E
F
G
H

A
-5
13
-

B
-5
4
2
10
-

C
13
4
21
7
12
-

D
21
8
-

E
78
6
-6

F
2
12
6
17
-

G
10
17
9

H
-6
9
-

Determine los caminos m´
ınimos en el grafo a partir del v´rtice A al H.
e

2.

Coloreo de grafos
Determine el n´merocrom´tico, χ(Gn ), del grafo Gn = (V, E ) definido a continuaci´n:
u
a
o
V = Z2n
E = {{i, i + 1} : i ∈ Z2n } ∪ {{i, i + n} : i ∈ Z2n }

3.

Matchings

Mediante el uso de la estrategia para hallar unmatching m´ximo descrita en el apunte, determine
a
si el representado en la figura 1 es m´ximo. En caso de que no lo sea, encu´ntre un matching m´ximo.
a
e
a

1

Figura 1: Un matching en ungrafo bipartito

4.

Grafos Tripartitos

Un grafo G = (V, E ) con χ(G) ≤ 3 se dice tripartito. Si los conjuntos de los v´rtices de cada color
e
son A, B y C , con |A| = i, |B| = j y |C| = k ,tal que hay arcos entre cada v´rtice en A y todos los
e
v´rtices en B y en C , y entre todos los v´rtices en B y en C , se le llama grafo tripartito completo y se
e
e
anota Ki,j,k .
1. ¿Cu´ntosv´rtices tiene Ki,j,k ?
a
e
2. ¿Cu´ntos arcos tiene Ki,j,k ?
a
3. ¿Para qu´ valores de i, j y k es regular este grafo?
e
4. ¿Para qu´ valores de i, j y k tiene un circuito o camino de Euler?
eCondiciones Generales
La tarea se realizar´ individualmente (esto es grupos de una persona), sin excepciones.
a
La tarea debe ser entregada impresa o manuscrita en clases o en la Secretar´ Docentede Inıa
form´tica (Piso 1, edificio F3) el d´ indicado en Moodle.
a
ıa
A
Opcionalmente, puede desarrollar la tarea en L TEX, lo cual tiene una bonificaci´n de 10 puno
tos. Para obtener la...