Modelos de gráficos y gráficos
La parte anterior presentó las diferentes herramientas para el razonamiento, la corrección y la resolución de problemas. En esta parte, estudiaremos las estructuras discretas que forman la base de la formulación de muchos problemas de la vida real.
Las dos estructuras discretas que cubriremos son gráficos y árboles. Un gráfico es un conjunto de puntos, llamados nodos o vértices, que están interconectados por un conjunto de líneas llamadas aristas. El estudio de gráficos, ograph theory es una parte importante de una serie de disciplinas en los campos de las matemáticas, la ingeniería y la informática.
¿Qué es un gráfico?
Definition - Un gráfico (denotado como $ G = (V, E) $) consiste en un conjunto no vacío de vértices o nodos V y un conjunto de aristas E.
Example - Consideremos, una gráfica es $ G = (V, E) $ donde $ V = \ lbrace a, b, c, d \ rbrace $ y $ E = \ lbrace \ lbrace a, b \ rbrace, \ lbrace a , c \ rbrace, \ lbrace b, c \ rbrace, \ lbrace c, d \ rbrace \ rbrace $
Degree of a Vertex - El grado de un vértice V de un gráfico G (denotado por deg (V)) es el número de aristas incidentes con el vértice V.
| Vértice | La licenciatura | Par / impar |
|---|---|---|
| un | 2 | incluso |
| segundo | 2 | incluso |
| C | 3 | impar |
| re | 1 | impar |
Even and Odd Vertex - Si el grado de un vértice es par, el vértice se llama vértice par y si el grado de un vértice es impar, el vértice se llama vértice impar.
Degree of a Graph- El grado de un gráfico es el grado de vértice más grande de ese gráfico. Para el gráfico anterior, el grado del gráfico es 3.
The Handshaking Lemma - En una gráfica, la suma de todos los grados de todos los vértices es igual al doble del número de aristas.
Tipos de gráficos
Existen diferentes tipos de gráficos, que aprenderemos en la siguiente sección.
Gráfico nulo
Un gráfico nulo no tiene bordes. El gráfico nulo de $ n $ vértices se denota por $ N_n $
Gráfico simple
Un gráfico se denomina gráfico simple / gráfico estricto si el gráfico no está dirigido y no contiene bucles ni bordes múltiples.
Multigrafo
Si en un gráfico se permiten múltiples aristas entre el mismo conjunto de vértices, se denomina Multigraph. En otras palabras, es un gráfico que tiene al menos un bucle o varios bordes.
Gráfico dirigido y no dirigido
Un gráfico $ G = (V, E) $ se llama gráfico dirigido si el conjunto de aristas está formado por un par de vértices ordenado y un gráfico se llama no dirigido si el conjunto de aristas está formado por un par de vértices desordenado.
Gráfico conectado y desconectado
Un gráfico está conectado si dos vértices cualesquiera del gráfico están conectados por una ruta; mientras que un gráfico está desconectado si al menos dos vértices del gráfico no están conectados por una ruta. Si un gráfico G está desconectado, entonces cada subgrafo conectado máximo de $ G $ se llama componente conectado del gráfico $ G $.
Gráfico regular
Una gráfica es regular si todos los vértices de la gráfica tienen el mismo grado. En una gráfica regular G de grado $ r $, el grado de cada vértice de $ G $ es r.
Gráfico completo
Una gráfica se llama gráfica completa si cada par de dos vértices está unido exactamente por una arista. El gráfico completo con n vértices se denota por $ K_n $
Gráfico de ciclo
Si un gráfico consta de un solo ciclo, se denomina gráfico de ciclo. El gráfico de ciclo con n vértices se denota por $ C_n $
Gráfica bipartita
Si el conjunto de vértices de un gráfico G se puede dividir en dos conjuntos disjuntos, $ V_1 $ y $ V_2 $, de tal manera que cada arista en el gráfico une un vértice en $ V_1 $ con un vértice en $ V_2 $, y no hay aristas en G que conecten dos vértices en $ V_1 $ o dos vértices en $ V_2 $, entonces el gráfico $ G $ se llama gráfico bipartito.
Gráfico bipartito completo
Un gráfico bipartito completo es un gráfico bipartito en el que cada vértice del primer conjunto se une a cada vértice del segundo conjunto. El gráfico bipartito completo se denota por $ K_ {x, y} $ donde el gráfico $ G $ contiene $ x $ vértices en el primer conjunto y $ y $ vértices en el segundo conjunto.
Representación de gráficos
Hay principalmente dos formas de representar un gráfico:
- Matriz de adyacencia
- Lista de adyacencia
Matriz de adyacencia
Una matriz de adyacencia $ A [V] [V] $ es una matriz 2D de tamaño $ V \ veces V $ donde $ V $ es el número de vértices en un gráfico no dirigido. Si hay una ventaja entre $ V_x $ y $ V_y $, entonces el valor de $ A [V_x] [V_y] = 1 $ y $ A [V_y] [V_x] = 1 $; de lo contrario, el valor será cero. Y para un gráfico dirigido, si hay un borde entre $ V_x $ y $ V_y $, entonces el valor de $ A [V_x] [V_y] = 1 $; de lo contrario, el valor será cero.
Adjacency Matrix of an Undirected Graph
Consideremos el siguiente gráfico no dirigido y construyamos la matriz de adyacencia:
La matriz de adyacencia del gráfico no dirigido anterior será:
a |
b |
c |
d |
|
a |
0 |
1 |
1 |
0 |
b |
1 |
0 |
1 |
0 |
c |
1 |
1 |
0 |
1 |
d |
0 |
0 |
1 |
0 |
Adjacency Matrix of a Directed Graph
Consideremos el siguiente gráfico dirigido y construyamos su matriz de adyacencia:
La matriz de adyacencia del gráfico dirigido anteriormente será:
a |
b |
c |
d |
|
a |
0 |
1 |
1 |
0 |
b |
0 |
0 |
1 |
0 |
c |
0 |
0 |
0 |
1 |
d |
0 |
0 |
0 |
0 |
Lista de adyacencia
En la lista de adyacencia, se usa una matriz $ (A [V]) $ de listas enlazadas para representar el gráfico G con $ V $ número de vértices. Una entrada $ A [V_x] $ representa la lista enlazada de vértices adyacentes al vértice $ Vx-th $. La lista de adyacencia del gráfico no dirigido es como se muestra en la siguiente figura:
Gráfico plano frente a gráfico no plano
Planar graph- Un gráfico $ G $ se llama gráfico plano si se puede dibujar en un plano sin bordes cruzados. Si dibujamos un gráfico en el plano sin cruzar los bordes, se llama incrustar el gráfico en el plano.
Non-planar graph - Un gráfico no es plano si no se puede dibujar en un plano sin que los bordes del gráfico se crucen.
Isomorfismo
Si dos gráficas G y H contienen el mismo número de vértices conectados de la misma manera, se denominan gráficas isomorfas (denotadas por $ G \ cong H $).
Es más fácil comprobar el no isomorfismo que el isomorfismo. Si ocurre alguna de las siguientes condiciones, entonces dos gráficos no son isomórficos:
- La cantidad de componentes conectados es diferente
- Las cardinalidades del conjunto de vértices son diferentes
- Las cardinalidades de los conjuntos de bordes son diferentes
- Las secuencias de grados son diferentes
Ejemplo
Los siguientes gráficos son isomórficos:
Homomorfismo
Un homomorfismo de un gráfico $ G $ a un gráfico $ H $ es un mapeo (Puede que no sea un mapeo biyectivo) $ h: G \ rightarrow H $ tal que - $ (x, y) \ in E (G) \ rightarrow (h (x), h (y)) \ en E (H) $. Mapea los vértices adyacentes del gráfico $ G $ a los vértices adyacentes del gráfico $ H $.
Propiedades de los homomorfismos
Un homomorfismo es un isomorfismo si es un mapeo biyectivo.
El homomorfismo siempre conserva los bordes y la conexión de un gráfico.
Las composiciones de homomorfismos también son homomorfismos.
Averiguar si existe alguna gráfica homomórfica de otra gráfica es un problema NPcompleto.
Gráficos de Euler
Un gráfico conectado $ G $ se llama gráfico de Euler, si hay un camino cerrado que incluye todos los bordes del gráfico $ G $. Una ruta de Euler es una ruta que usa cada borde de un gráfico exactamente una vez. Un camino de Euler comienza y termina en diferentes vértices.
Un circuito de Euler es un circuito que usa cada borde de un gráfico exactamente una vez. Un circuito de Euler siempre comienza y termina en el mismo vértice. Un gráfico conectado $ G $ es un gráfico de Euler si y solo si todos los vértices de $ G $ son de grado par, y un gráfico conectado $ G $ es euleriano si y solo si su conjunto de aristas se puede descomponer en ciclos.
El gráfico anterior es un gráfico de Euler como $ “a \: 1 \: b \: 2 \: c \: 3 \: d \: 4 \: e \: 5 \: c \: 6 \: f \: 7 \: g ”$ cubre todos los bordes del gráfico.
Gráficos hamiltonianos
Un gráfico conectado $ G $ se llama gráfico hamiltoniano si hay un ciclo que incluye cada vértice de $ G $ y el ciclo se llama ciclo hamiltoniano. La caminata hamiltoniana en el gráfico $ G $ es una caminata que pasa por cada vértice exactamente una vez.
Si $ G $ es un gráfico simple con n vértices, donde $ n \ geq 3 $ Si $ deg (v) \ geq \ frac {n} {2} $ para cada vértice $ v $, entonces el gráfico $ G $ es Gráfico hamiltoniano. Se llamaDirac's Theorem.
Si $ G $ es un gráfico simple con $ n $ vértices, donde $ n \ geq 2 $ si $ deg (x) + deg (y) \ geq n $ para cada par de vértices no adyacentes xey, entonces el el gráfico $ G $ es un gráfico hamiltoniano. Se llamaOre's theorem.
