Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

GRAFO SIMPLE

No description
by

Alexis Osnaya

on 19 May 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of GRAFO SIMPLE

Sean V1 y V2 el conjunto de vértices de grado par e impar de un grafo no dirigido G=(V, E). Entonces:





Como delta de v es par si v está en V1, el primer sumando del término de la derecha de la última igualdad es par. Además, la suma de los dos sumado s de dicho término es par puesto que su suma es 2e, por tanto el 2 sumando también es par. Como todos los términos que se suman en este 2 sumando son impares, tiene que haber un número par de ellos por tanto hay un número par de vértices de grado impar.
GRAFO SIMPLE
Grafos definidos a partir de otros
MULTIGRAFO
GRAFO DIRIGIDO
8.2 Terminología
Se dice que 2 vértices u y v de un grafo no dirigido G son adyacentes en G si {u, v}es una arista de G. Si e={u, v}, se dice que la arista e es incidente con los vértices u y v. Se dice que los vértices u y v son extremos de la arista e. El grado de vértice de un grafo no dirigido es el número de aristas incidentes con él, excepto los bucles.
Demostración:
GRAFOS
¡GRACIAS!
Un grafo simple G=(V,E) consta de V, un conjunto no vacío de vértices, y de E, un conjunto de pares no ordenados de elementos distintos de V. A estos pares se les llama aristas.
Esta representado por vértices y aristas no dirigidas.
Un multigrafo G=(V,E) consta de un conjunto V de vértices, un conjunto E de aristas y una función f de E en {{u,v}|u,v pertenece V, U diferente V}. Se dice que las aristas e1 y e2 son aristas múltiples o paralelas si f(e1)=f(e2).
Múltiples caminos entre dos vértices.
PSEUDOGRAFO
Son aristas que van de un vértice así mismo (bucle).
Un pseudografo G=(V,E) consta de un conjunto V de vértices, un conjunto E de arista y una función f de E en {{u,v}|u,v pertenece V}. Una arista e es un bucle, o lazo, si f(e)={u,u}={u} para algún u pertenece V.
Un grafo dirigido (V,E) consta de un conjunto V de vértices y de un conjunto E de aristas. que son pares ordenados de elementos de V
Utilizamos una flecha apuntando desde u hacia v para indicar las dirección de la arista (u,v).
MULTIGRAFO DIRIGIDO
Un multigrafo dirigido G=(V,E) consta de un conjunto V de vertices, un conjunto E de aristas y una función f de E en {(u,v)|u,v pertenece V}. Se dice que las aristas e1 y e2 son aristas múltiples si f(e1)=f(e2).
Existe mas de una arista con dirección entre cada par de vértice.
TABLA
EJEMPLOS
Teorema del apretón de manos
El teorema 1 nos dice que la suma de los grados de los vértices de un grafo no dirigido es un número par, una consecuencia de esto es.

Teorema 2. Todo grafo no dirigido tiene un número par de vértices de grado impar.
Si (u, v) es un arista del grafo dirigido G, se dice que u es adyacente a v y que v es adyacente desde u. Al vértice u se le llama vértice inicial de (u, v) y a v se le llama vértice final o terminal de (u, v). Los vértices inicial y final de un bucle coinciden.
En un grafo dirigido, el grado de entrada de un vértice v,, es el número de aristas que tienen a v como vértice final. El grado de salida de un vértice v, es el número de aristas que tienen como vértice inicial a v.
Grafos Bipartitos
Se dice que un grafo simple G es bipartito si su conjunto de vértices V se puede dividir en 2 conjuntos disjuntos V1 y V2 tales que cada arista del grafo conecta un vértice de V con un vértice de V2.
Como cada arista tiene un vértice inicial y uno final, la suma de los grados de entrada y la suma de los grados de salida de todos los vértices del grafo dirigido coinciden. Ambas sumas son iguales al número de aristas que tiene el grafo.
Un subgrafo de un grafo G=(V E) es un grafo H=(W, F) con W subconjunto de V y F subconjunto de E.
La unión de dos grafos simples G1=(V1, E1) y G2=(V2, E2) es el grafo simple cuyo conjunto de vértice es V1UV2 y cuyo cojunto de aristas es E1UE2. La unión de G1 y G2 se denota como G1UG2.
si grado(v)=k para todos los vértices v, entonces es k-regular. como dice el teorema 2e=20=4v
Full transcript