Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
DEFINICION
Grafos
| Term | Definition |
|---|---|
| Grafo | es una estructura matematica que consta de dos conjuntos V y E. Los elementos de V se llaman vertices o nodos y los elementos de E se llaman aristas. Cada arista tiene un conjunto de uno o mas vertices asociados que se llaman puntos extremos. (V ̸= ∅) |
| Grafo trivial | #V = 1 y #E = 0 |
| Lazo | Es una arista cuyos puntos extremos son coincidentes. |
| Arista Propia | Es una arista que no es un lazo. |
| Multigrafo | existen a y b ∈ V con dos o mas aristas incidentes en a y b. En caso contrario se llama grafo simple. |
| Grafo dirigido o digrafo | Es un grafo que tiene todas sus aristas dirigidas. |
| Multigrafo dirigido | existen a, b ∈ V con dos o mas aristas de la forma (a, b). En caso contrario se llama digrafo simple. |
| Matriz de incidencia | IG[v, e] =0 si v no es un extremo de e; 1 si v es un extremo de e; 2 si e es un lazo en v. Si es un digrafo: ID[v, e] = 0 si v es un extremo de e ; 1 si v es la cabeza de e ; −1 si v es la cola de e; 2 si e es un lazo de v. |
| Matriz de adyacencia | AG[u, v] = la cantidad de aristas entre ellos si u ̸= v; la cantidad de lazos si v = u |
| Grado | El grado de un vertice en un grafo G denotado g(v) es el numero de aristas propias incidentes en v mas el doble del numero de lazos en v. |
| Grafo completo | Es un grafo simple sin lazos tal que todo par de vertices estan unidos por una arista. notacion: Kn |
| Grafo bipartito | Un grafo G = (V,E) es bipartito si V = V1 ∪ V2, V1 ∩ V2 = ∅ y cada arista de G es de la forma a, b donde a ∈ V1 y b ∈ V2. Si cada vertice de V1 esta unido con todos los vertices de V2, se tiene un grafo bipartito completo. |
| Grafo regular | Todos los vertices tienen el mismo grado. Se llama k-regular si todos los vertices tienen grado k (Grafos Kn son (n-1) regulares) |
| Subgrafo | Un subgrafo de un grafo G (dirigido o no) es un grafo H, que cumple que VH ⊆ VGy EH ⊆ EG |
| Subgrafo recubridor | H es un subgrafo recubridor de G si VG = VH. |
| Subgrafo inducido | el subgrafo de G inducido por U es el subgrafo cuyo conjunto de vertices es U y que contiene todas las aristas de G |
| Borrado de un vertice | G − v es el subgrafo inducido por el conjunto de vertices VG − {v}. |
| Borrado de una arista | G − e es el subgrafo cuyo conjunto de aristas es EG − {e} y el conjunto de vertices es VG |
| Agregado de vertice | supergrafo denotado GU{v} donde el conjunto de es VGU{v} y el conjunto de aristas es EG. |
| Agregado de arista | supergrafo denotado GU{e} donde el conjunto de vertices es VG y el conjunto de aristas es EG ∪ {e} |
| Suma de grafos | Sumando G y H se obtiene VG+H = VG∪VH y EG+H = EG ∪ EH ∪ {e = {u, v} : u ∈ VG, v ∈ VH} |
| Complemento | G¯ o Gc es el subgrafo de Kn formado por los n vertices de G y todas las aristas que no estan en G. |
| Isomorfismo de grafos | Sean G1 (V1, E1) y G2 (V2, E2) dos grafos no dirigidos, una funcion f : V1 → V2 es un isomorfismo de grafos si: 1. f es biyectiva. 2. ∀a, b ∈ V1, {a, b} ∈ E1 ⇔ {f(a), f(b)} ∈ E2 Notacion: G1 ≃ G2. |
Created by:
procer
Popular Math sets