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
Camino
| Term | Definition |
|---|---|
| Camino | secuencia alternada w = < v0, e1, v1, e2, v2, ... , vn-1, en, vn> de vertices y aristas ei = {vi-1, vi} |
| Camino Directo | en un digrafo de v0 a vn es una secuencia alternada w = < v0, e1, v1, e2, v2, ... , vn-1, en, vn> de vertices y aristas ei = (vi-1, vi) con i = 1,...,n. Not: v0 - vn |
| Longitud de camino | La longitud de un camino o camino directo es el n´umero de aristas que recorre el camino |
| Camino Cerrado | Un camino o camino directo x-y es cerrado si x = y, si no, es abierto |
| Concatenacion de caminos | La concatenaci´on de dos caminos w1 =< v0, e1, v1, e2, ..., vk−1, ek, vk > y w2 =< vk, ek+1, vk+1, ek+2, ..., vn−1, en, vn > tal que w2 empieza donde termina w1 es el camino w1 ◦ w2 =< v0, e1, v1, e2, ..., vn−1, en, vn > |
| Subcamino | un subcamino es una subsecuencia de entradas consecutivas que comienza y termina en un vertice. un subcamino es un camino |
| Vertice alcanzable | un vertice v es alcanzable desde un vertice u si existe un camino u-v |
| Conexidad | un grafo es conexo si para todo par de vertices u y v hay un camino u-v |
| Digrafo conexo | es conexo debilmente si al considerarlo no dirigido es conexo. y es fuertemente conexo si para todo par de vertices en el digrafo es mutuamente alcanzable. |
| Distancia | es la longitud del camino mas corto de un vertice a otro. infinito si no existe camino |
| Reduccion de un camino | dado un camino que contiene un subcamino cerrado. (borra los ciclos) |
| Recorrido | Es un camino que no repite aristas |
| Camino simple | Es un camino que no repite vertices |
| Circuito | es un recorrido cerrado |
| Ciclo | es un camino simple cerrado |
| Coleccion de ciclos de aristas disjuntas | una descomposicion de un circuito T si los Gi son subcaminos de T y Et = UEgi y la interseccion es vacia |
| Recorrido euleriano | recorrido que contiene todas las aristas del grafo |
| Circuito euleriano | es un recorrido euleriano cerrado |
| Grafo euleriano | si tiene un circuito euleriano |
| Camino hamiltoniano | camino simple (no ciclo) en el grafo que contiene todos sus vertices |
| Ciclo hamiltoniano | G grafo y #V >= 3 G tiene un ciclo hamiltoniano si existe un ciclo en G que contenga cada vertice |
Created by:
procer
Popular Math sets