Zusammenfassung der Ressource
Introducción a la teoría de gráficas
- ¿Qué es una gráfica?
- Conjunto de vértices, nodos o puntos unidos por aristas, líneas o arcos que pueden, o no, ser con dirección
- Tipos de gráficas
- Multigrafo o pseudografo
- Es aquella que tiene múltiples aristas
- Nula
- No contiene aristas
- Simple
- No contiene bucles ni líneas paralelas
- General
- Contiene bucles y líneas paralelas
- Finitas o infinitas (a criterio de sus nodos)
- Regular
- Debe ser una gráfica simple y los grados de sus nodos deben ser iguales
- Subgráficas
- Todos los vértices de g están contenidos en G
- Cada línea de g tiene los mismos vértices terminales en G
- G es subgráfica de g; subgráfica de g es subgráfica de G; un vértice es subgráfica de G; un arco con sus respectivos nodos es una subgráfica de G
- Isomórfica
- Dos gráficas que comparten la relación entre sus nodos y sus arcos aún siendo graficadas de diferente forma
- Digráfica o gráfica dirigida
- Multidigrafo: digrafo con múltiples aristas
- Pseudografo: multidigrafo con bucles
- Longitud y distancia
- Número de líneas que contiene un paseo
- Entre dos nodos, es la distancia del paseo mínimo que los une
- Bloque
- Separada
- Paseos
- Secuencia de pasos finita y alterna de nodos y arcos comenzando y terminando en un nodo de cada línea tal que sean incidentes con nodos anteriores y posteriores
- Abiertos
- Trayectoria simple: no se repiten nodos ni arcos
- Cerrados
- Circuito: no se repiten nodos ni arcos salvo el nodo inicial y el nodo final
- Árboles
- Árbol
- Árbol binario
- Árbol estrictamente binario
- El tamaño es el número de arcos en G
- Arcos
- Dirigido
- Crean una gráfica dirigida ó bigráfica
- No Dirigido
- Paralelos
- Si dos arcos NO paralelos inciden en un nodo, se dice que son adyacentes
- El número de líneas que inciden en un nodo es llamado grado ó valencia " d(Vi)"
- El orden es el número de nodos en G
- Nodos
- Nodo terminal
- Cuando un nodo es terminal de un arco, se dice que estos son incidentes
- Cuando dos arcos comparten una línea en común, son adyacentes
- Bucle
- Grado
- Externo
- Interno
- Articulación
- Aquel nodo al que, si se elimina, desconecta a G
- Teoremas
- Si una gráfica sin bucles tiene e líneas y n vértices, la suma del grado de sus vértices es igual a dos veces al número de líneas.
- El número de vértices de grado impar en una gráfica sin bucles es par
- Un nodo aislado tiene valencia o grado 0
- Un nodo de grado 1 se le llama nodo colgante, pendiente o final
- La suma de los grados internos es igual a la suma de los grados externos y es igual al número de líneas que contiene un grafo