Practica 3 Y 4 Gustavo Uzcategui

1.1.1 Practica 3
Con la ayuda de MaGraDa se han de realizar los siguientes ejercicios relacionados con los fundamentos de grafos.
Problema 2.1. Consideremos el grafo no dirigido que apa- rece en la siguiente figura:


(i) Calcula a mano el grado de cada vértice. Comprueba el resultado con MaGraDa, desde el modo gráfico.
Grado vertice a = 1
Grado vertice b = 3
Grado vertice c = 4
Grado vertice d= 4
Grado vertice e = 4
Grado vertice f = 2
Grado vertice g = 2









(ii) Relaciona el grado de los vértices con el número de aris- tas. Exprésalo también de forma matemática para cual- quier grafo.

G(a) = ΣA(1)+2(0) = 1
G(b) = ΣA(3)+2(0) = 3
G(c) = ΣA(2)+2(1) = 4
G(d) =ΣA(2)+2(1) = 4
G(e) = ΣA(4)+2(0) = 4
G(f) = ΣA(2)+2(0) = 2
G(h) = ΣA(2)+2(0) = 2
Matemáticamente para cualquier grafo: G(vi) = ΣA(i) + 2Bu


(iii) Con la ayuda de MaGraDa, di si el grafo es completo o no y explica el porqué.

El grafo no es complete ya que no existe ninguna arista entre los vertices a y c.

Problema 2.2. Consideremos el siguiente grafo dirigido:

(i) Calcula a mano el grado de entrada y de salida de cada vértice. Comprueba el resultado con MaGraDa, desde el modo gráfico.

Grado vertice a Entrada = 1Salida = 3
Grado vertice b Entrada = 8 Salida = 8
Grado vertice c Entrada = 2 Salida = 1
Grado vertice d Entrada = 1 Salida = 2
Grado vertice e Entrada = 2 Salida = 0









(ii) Relaciona el grado de los vértices (tanto de entrada co- mo de salida) con el número de arcos. Exprésalo tam- bién de forma matemática para cualquier grafo.

a = Σ(1); Σ(3) = 4
b = Σ(1); Σ(2) = 2c = Σ(2); Σ(1) = 1
c =Σ(1); Σ(2) = 3
d = Σ(2); Σ(0) = 2

Forma matematica
ΣAin; ΣAout(iii)



(iii) Con la ayuda de MaGraDa, di si el grafo es cíclico o no y explica el porqué.

El grafo si es ciclico porque en el vertice a aparace un ciclo

(iv) Con la ayuda de MaGraDa, di si el grafo es un multigrafo o no y explica el porqué.

No es multigrafo porque no hay dos aristas que unan dos mismo vertices

(v) Con la ayuda deMaGraDa y tus conocimientos actuales, di si el grafo es conexo o no y explica el porqué.

No es conexo ya que tiene mas de una componente conexa


(vi) Con la ayuda de MaGraDa, di si el grafo es débilmente conexo o no y explica el porqué.

No es debilmente conexo ya que no existen caminos entre todos los vertices
Problema 2.3. La siguiente figura nos da dos grafos dibu- jados como las letras F yT.


Comprueba y razona que los grafos F y T son grafos isomor- fos.
Si los grafos F y T son isomorfos

Problema 2.4. Consideremos que se tiene un grafo, que tiene 8 aristas y 5 vértices. Se sabe además que tiene 4 vértices de grado 3.
(i) Explica razonadamente de qué grado es el otro vértice

El vertice restante seria de grado 4

(ii) Dibuja con MaGraDa un grafo no dirigido y sin bucles con esascaracterísticas. Presenta dicho grafo en tu práctica.






(iii) Desde MaGraDa, elimina de tu grafo el vértice que tie- ne grado 4. Razona, sin que el dibujo del grafo te sirva para tu explicación, cuántas aristas te quedarán en el
grafo y comprueba que sigue cumpliéndose la relación matemática entre vértices y aristas. Comprueba con Ma- GraDa que tus razonamientos han sido válidos.Quedarian 4 aristas y 4 vertices cumpliendose la relacion matematica, se puede observer la comprobacion en magrada





Problema 2.5. Consideremos que se tiene un grafo no di- rigido que tiene 5 aristas y sólo tiene vértices de grado 3 y de grado 2.
(i) Explica cuántos vértices tiene de cada tipo.

Dos vertices de grado 3 y dos vertices de grado 2

(ii) Dibuja con MaGraDa un grafo no dirigido y simple quecumpla estas características y muestra con MaGraDa que tu razonamiento ha sido válido.
2.3.1 Práctica 4
En esta práctica vamos a familiarizarnos con el concepto de matriz de adyacencia y sus propiedades.

Problema 2.6. Consideremos el grafo dirigido de la si- guiente figura:

(i) Introduce el grafo en MaGraDa mediante su matriz de adyacencia. Visualízala y escríbela en tu práctica.



(ii)...