Introduccinalateoradegrafos2014paraimprimir2 141216184112 Conversion Gate01
Páginas: 4 (852 palabras)
Publicado: 1 de septiembre de 2015
Una introducción
a la teoría de grafos
Matemática Discreta
UADE
Definición
Un grafo finito es una estructura
caracterizada por un conjunto de
vértices o nodos V = {v1, v2, …, vn} y
un conjunto delados o aristas
A = {a1, a2, …, am} tal que cada arista
tiene como extremos dos vértices
sobre los cuales incide.
Matemática Discreta - UADE
Representación gráfica
Los grafos finitos puedenrepresentarse
mediante un diagrama o esquema
Ejemplo de grafo:
Matemática Discreta - UADE
Definición
Un digrafo finito es una estructura
caracterizada por un conjunto de
vértices o nodos V = {v1, v2, …, vn}y
un conjunto de lados o aristas A = {a1,
a2, …, am} tal que cada arista tiene
fijado un sentido e incide sobre dos
vértices, negativamente sobre su origen
o extremo inicial y positivamente sobre
sudestino o extremo final.
Matemática Discreta - UADE
Representación gráfica
Los digrafos finitos pueden
representarse gráficamente
Ejemplo de digrafo:
Matemática Discreta - UADE
Algunasdefiniciones
relativas a grafos y digrafos
Dos vértices relacionados por medio
de una arista son adyacentes.
Dos aristas con un único extremo en
común son adyacentes.
Dos aristas con los mismosvértices
de incidencia son paralelas.
Una arista cuyos extremos coinciden
es un lazo.
Un grafo o digrafo que carece de
aristas paralelas y lazos es simple.
Matemática Discreta - UADE
Grado o valenciade un vértice
En grafos:
En digrafos:
El grado de un
El grado positivo
vértice es la
(negativo) de un
cantidad de aristas
vértice es la
que inciden en ese
cantidad de aristas
vértice (el lazo
queinciden
cuenta doble).
positivamente
Se anota g(v)
(negativamente)
Se cumple que
en ese vértice.
g (vi ) = 2 |A|
Se anota g+(v)
(g -(v))
Matemática Discreta - UADE
Grado o valencia de unvértice
en un digrafo
El grado total de un vértice es la suma
del grado positivo y el grado negativo.
El grado neto de un vértice es el grado
positivo menos el grado negativo.
Se verifica...
a la teoría de grafos
Matemática Discreta
UADE
Definición
Un grafo finito es una estructura
caracterizada por un conjunto de
vértices o nodos V = {v1, v2, …, vn} y
un conjunto delados o aristas
A = {a1, a2, …, am} tal que cada arista
tiene como extremos dos vértices
sobre los cuales incide.
Matemática Discreta - UADE
Representación gráfica
Los grafos finitos puedenrepresentarse
mediante un diagrama o esquema
Ejemplo de grafo:
Matemática Discreta - UADE
Definición
Un digrafo finito es una estructura
caracterizada por un conjunto de
vértices o nodos V = {v1, v2, …, vn}y
un conjunto de lados o aristas A = {a1,
a2, …, am} tal que cada arista tiene
fijado un sentido e incide sobre dos
vértices, negativamente sobre su origen
o extremo inicial y positivamente sobre
sudestino o extremo final.
Matemática Discreta - UADE
Representación gráfica
Los digrafos finitos pueden
representarse gráficamente
Ejemplo de digrafo:
Matemática Discreta - UADE
Algunasdefiniciones
relativas a grafos y digrafos
Dos vértices relacionados por medio
de una arista son adyacentes.
Dos aristas con un único extremo en
común son adyacentes.
Dos aristas con los mismosvértices
de incidencia son paralelas.
Una arista cuyos extremos coinciden
es un lazo.
Un grafo o digrafo que carece de
aristas paralelas y lazos es simple.
Matemática Discreta - UADE
Grado o valenciade un vértice
En grafos:
En digrafos:
El grado de un
El grado positivo
vértice es la
(negativo) de un
cantidad de aristas
vértice es la
que inciden en ese
cantidad de aristas
vértice (el lazo
queinciden
cuenta doble).
positivamente
Se anota g(v)
(negativamente)
Se cumple que
en ese vértice.
g (vi ) = 2 |A|
Se anota g+(v)
(g -(v))
Matemática Discreta - UADE
Grado o valencia de unvértice
en un digrafo
El grado total de un vértice es la suma
del grado positivo y el grado negativo.
El grado neto de un vértice es el grado
positivo menos el grado negativo.
Se verifica...
Leer documento completo
Regístrate para leer el documento completo.