GRAFOS

Páginas: 71 (17686 palabras) Publicado: 16 de febrero de 2016
Apuntes de Matem´atica Discreta
14. Grafos

Francisco Jos´e Gonz´alez Guti´errez
C´adiz, Octubre de 2004

Universidad de C´
adiz

Departamento de Matem´
aticas

ii

Lecci´
on 14

Grafos
Contenido
14.1 Generalidades . . . . . . . . . . . . . . . . . . .
14.1.1 Definici´
on . . . . . . . . . . . . . . . . . . . .
14.1.2 V´ertices Adyacentes . . . . . . . . . . . . . .
14.1.3 Representaci´
on Gr´afica . . . . . . . . . . . .
14.1.4 Multigrafos . . . . . . . . . . . . . . . . . . .
14.1.5 Pseudografo . . . . . . . . . . . . . . . . . . .
14.1.6 Digrafo . . . . . . . . . . . . . . . . . . . . .
14.2 Grados . . . . . . . . . . . . . . . . . . . . . . .
14.2.1 Grado de un V´ertice . . . . . . . . . . . . . .
14.2.2 V´ertice Aislado . . . . . . . . . . . . . . . . .
14.2.3 Grafo Regular . . .. . . . . . . . . . . . . . .
14.2.4 Suma de los Grados de un Grafo . . . . . . .
14.2.5 Grado de Entrada y de Salida . . . . . . . . .
14.3 Isomorfismo . . . . . . . . . . . . . . . . . . . .
14.3.1 Isomorfismo de Grafos . . . . . . . . . . . . .
14.3.2 Invariante de un Grafo . . . . . . . . . . . . .
14.3.3 Invariancia del Grado . . . . . . . . . . . . .
14.4 Subgrafos . . . . . . . . . . . . .. . . . . . . .
14.4.1 Definici´
on . . . . . . . . . . . . . . . . . . . .
14.4.2 Subgrafo Expandido . . . . . . . . . . . . . .
14.4.3 Subgrafo Inducido . . . . . . . . . . . . . . .
14.4.4 Eliminaci´
on de Aristas . . . . . . . . . . . . .
14.4.5 Eliminaci´
on de V´ertices . . . . . . . . . . . .
14.4.6 Grafos Completos . . . . . . . . . . . . . . .
14.4.7 Complemento de un Grafo . . . . . . .. . . .
14.5 Caminos y Ciclos . . . . . . . . . . . . . . . . .
14.5.1 Camino . . . . . . . . . . . . . . . . . . . . .
14.5.2 Ciclo . . . . . . . . . . . . . . . . . . . . . . .
14.5.3 Teorema . . . . . . . . . . . . . . . . . . . . .
14.6 Grafos Conexos . . . . . . . . . . . . . . . . . .
14.6.1 V´ertices Conectados . . . . . . . . . . . . . .
14.6.2 Grafos Conexos . . . . . . . . . . . . . . .. .
14.6.3 Proposici´
on . . . . . . . . . . . . . . . . . . .
14.6.4 Componentes Conexas de un Grafo . . . . . .
14.6.5 Puntos de Corte . . . . . . . . . . . . . . . .
14.6.6 Puentes . . . . . . . . . . . . . . . . . . . . .

395

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.

. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . .. .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .396
396
397
397
398
398
399
399
399
399
399
400
402
403
403
404
404
406
406
407
407
408
408
409
410
411
411
411
413
414
414
414
415
416
418
418

Universidad de C´
adiz

Departamento de Matem´
aticas

14.7 Caminos y Ciclos de Euler . . . . . . . . . . .
14.7.1 Ciclo de Euler . . . . . . . . . . . . . . . . .
14.7.2 Grafo Euleriano . . . . . . . . . . . . . . . . .
14.7.3 Primer Lema . . . . . . . ....
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • grafos

    ...jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj- jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj- jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj- jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj- jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj- jjjjjjjjjjjj .- Que es un documento Es todo aquel material que emite una información, satélite, película, archivo, teléfono, envase, foto. 2.- Cuales son los tipos de escritura...

    Leer más
    1296 Palabras 6 Páginas
  • Grafos

    ...EDA Grafos Lengoaia eta sistema informatikoak UPV-EHU Jesús Bermudez-en gardenkietan oinarrituta Eta haren Creative Commons baimenekin zabaldua EDA ¿Qué es un grafo?  G=(N, A) – N es un conjunto de nodos (o vértices) – A es un conjunto de arcos (par de nodos) A C E B D {A, C} {B, C} {A, B} {D, B} {A, E} {E, D} A C E B D (A, C) (C, B) (A, B) (B, D) (E, A) (D, E) NO dirigido Grafoak/Grafos dirigido 2 EDA...

    Leer más
    828 Palabras 4 Páginas
  • Grafos

    ...NOVIEMBRE DEL 2010 *GRAFOS Un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan...

    Leer más
    999 Palabras 4 Páginas
  • Grafos

    ...Curso de doctorado “Problemas de optimizaci´n sobre grafos” o Departament de Matem`tica a Conceptos b´sicos sobre grafos y digrafos a Definici´n de grafo o Un grafo G = (V, E) est´ formado por un conjunto finito y no vac´ V y por un conjunto E de a ıo pares no ordenados de elementos distintos de V . Elementos de V : v´rtices (o nodos). e Elementos de E: aristas. Si e = {u, v} (e = uv) es una arista, entonces u y v son adyacentes (u...

    Leer más
    1571 Palabras 7 Páginas
  • grafo

    ... Practica 7 # La Caza Y La Pesca 1. ¿Qué animales se cazan en el mundo? La caza Los temas relacionados con el control de vida silvestre no se limitan a problemas que tienen lugar dentro de los parques nacionales. En muchas partes de mundo, por ejemplo, las poblaciones de ciervos se han convertido en un problema debido a la progresiva reducción de las áreas naturales. A medida que el crecimiento humano penetra cada vez más en el hábitat de los ciervos, éstos y las personas van teniendo...

    Leer más
    1066 Palabras 5 Páginas
  • Grafos

    ...GRAFOS Definición Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos. Cada arco en un grafo se especifica por un par de nodos. El...

    Leer más
    823 Palabras 4 Páginas
  • Grafos

    ... UNIDAD II: Relaciones Y GRAFOS SESIÓN 11 : DIAGRAMAS DE HASSE NIVEL 1 a. Defina que es una relación de orden parcial. b. Defina que es una relación de orden lineal c. Determine a partir de cuáles de los siguientes dígrafos se pueden construir diagramas de Hasse a) b) c) d. Describa los pares ordenados de la relación de orden representados en el siguiente diagrama de Hasse e.- Describa los pares ordenados de la...

    Leer más
    1334 Palabras 6 Páginas
  • Grafos

    ...TALLER DE GRAFOS 1-Sea el grafo G=( {V1, V2, V3, V4, V5, V6,}, { V1V2, V1V3, V1V4, V1V6, V2V3, V2V4, V2V6, V3V6, V4V5, V5V6}): a) Haga un esquema del mismo [pic] b) Determine un camino simple de V1 a V5 de longitud 5. • (V1, V6, V2, V3, V4, V5) [pic] c) Escriba un ciclo simple de V5 a V5, con la mayor longitud posible. (V5, V6, V1, V2,V3 , V4, V5)). Longitud 6. [pic] D) Determine si es euleriano. Justifique su respuesta Si es euleriano...

    Leer más
    1086 Palabras 5 Páginas

OTRAS TAREAS POPULARES

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS