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