Teoría de grafos - Fundamentos
Un gráfico es un diagrama de puntos y líneas conectados a los puntos. Tiene al menos una línea que une un conjunto de dos vértices sin vértice que se conecta a sí mismo. El concepto de grafos en la teoría de grafos se basa en algunos términos básicos como punto, línea, vértice, borde, grado de vértices, propiedades de grafos, etc. Aquí, en este capítulo, cubriremos estos fundamentos de la teoría de grafos.
Punto
A pointes una posición particular en un espacio unidimensional, bidimensional o tridimensional. Para una mejor comprensión, un punto se puede denotar con un alfabeto. Se puede representar con un punto.
Ejemplo
Aquí, el punto es un punto llamado 'a'.
Línea
UN Linees una conexión entre dos puntos. Se puede representar con una línea continua.
Example
Aquí, 'a' y 'b' son los puntos. El vínculo entre estos dos puntos se llama línea.
Vértice
Un vértice es un punto donde se encuentran varias líneas. También se llamanode. Similar a los puntos, un vértice también se denota con un alfabeto.
Example
Aquí, el vértice se nombra con un alfabeto 'a'.
Borde
Una arista es el término matemático para una línea que conecta dos vértices. Se pueden formar muchas aristas a partir de un solo vértice. Sin un vértice, no se puede formar una arista. Debe haber un vértice inicial y un vértice final para una arista.
Example
Aquí, 'a' y 'b' son los dos vértices y el vínculo entre ellos se llama borde.
Grafico
Un gráfico 'G' se define como G = (V, E) Donde V es un conjunto de todos los vértices y E es un conjunto de todos los bordes del gráfico.
Example 1
En el ejemplo anterior, ab, ac, cd y bd son los bordes del gráfico. De manera similar, a, b, cyd son los vértices de la gráfica.
Example 2
En este gráfico, hay cuatro vértices a, b, cyd, y cuatro aristas ab, ac, ad y cd.
Lazo
En un gráfico, si se dibuja una arista desde el vértice hacia sí misma, se denomina bucle.
Example 1
En el gráfico anterior, V es un vértice para el cual tiene un borde (V, V) que forma un bucle.
Example 2
En este gráfico, hay dos bucles que se forman en el vértice ay el vértice b.
Grado de vértice
Es el número de vértices adyacentes a un vértice V.
Notation - grados (V).
En una gráfica simple con n número de vértices, el grado de cualquier vértice es -
grados (v) ≤ n - 1 ∀ v ∈ G
Un vértice puede formar una arista con todos los demás vértices excepto por sí mismo. Entonces, el grado de un vértice estará hasta elnumber of vertices in the graph minus 1. Este 1 es para el auto-vértice, ya que no puede formar un bucle por sí mismo. Si hay un bucle en cualquiera de los vértices, entonces no es un gráfico simple.
El grado de vértice se puede considerar en dos casos de gráficos:
Gráfico no dirigido
Gráfico dirigido
Grado de vértice en un gráfico no dirigido
Un gráfico no dirigido no tiene bordes dirigidos. Considere los siguientes ejemplos.
Example 1
Eche un vistazo al siguiente gráfico:
En el gráfico no dirigido anterior,
deg (a) = 2, ya que hay 2 aristas que se encuentran en el vértice 'a'.
deg (b) = 3, ya que hay 3 aristas que se encuentran en el vértice 'b'.
deg (c) = 1, ya que hay 1 borde formado en el vértice 'c'
Entonces 'c' es un pendent vertex.
deg (d) = 2, ya que hay 2 aristas que se encuentran en el vértice 'd'.
deg (e) = 0, ya que hay 0 aristas formadas en el vértice 'e'.
Entonces 'e' es un isolated vertex.
Example 2
Eche un vistazo al siguiente gráfico:
En el gráfico anterior,
deg (a) = 2, deg (b) = 2, deg (c) = 2, deg (d) = 2 y deg (e) = 0.
El vértice 'e' es un vértice aislado. El gráfico no tiene ningún vértice colgante.
Grado de vértice en un gráfico dirigido
En una gráfica dirigida, cada vértice tiene una indegree y un outdegree.
Grado de un gráfico
El grado de indecisión del vértice V es el número de aristas que entran en el vértice V.
Notation - grados− (V).
Grado superior a un gráfico
El grado exterior del vértice V es el número de aristas que salen del vértice V.
Notation - grados + (V).
Considere los siguientes ejemplos.
Example 1
Eche un vistazo al siguiente gráfico dirigido. El vértice 'a' tiene dos bordes, 'ad' y 'ab', que van hacia afuera. Por lo tanto, su grado externo es 2. De manera similar, hay un borde 'ga', que viene hacia el vértice 'a'. Por tanto, el grado de 'a' es 1.
En la siguiente tabla se muestra el grado y el grado de salida de otros vértices:
| Vértice | Indegree | Outdegree |
|---|---|---|
| un | 1 | 2 |
| segundo | 2 | 0 |
| C | 2 | 1 |
| re | 1 | 1 |
| mi | 1 | 1 |
| F | 1 | 1 |
| gramo | 0 | 2 |
Example 2
Eche un vistazo al siguiente gráfico dirigido. El vértice 'a' tiene una arista 'ae' que va hacia afuera desde el vértice 'a'. Por lo tanto, su grado externo es 1. De manera similar, el gráfico tiene un borde 'ba' que se acerca al vértice 'a'. Por tanto, el grado de 'a' es 1.
En la siguiente tabla se muestra el grado y el grado de salida de otros vértices:
| Vértice | Indegree | Outdegree |
|---|---|---|
| un | 1 | 1 |
| segundo | 0 | 2 |
| C | 2 | 0 |
| re | 1 | 1 |
| mi | 1 | 1 |
Vértice colgante
Al usar el grado de un vértice, tenemos dos tipos especiales de vértices. Un vértice con grado uno se llama vértice colgante.
Example
Aquí, en este ejemplo, el vértice 'a' y el vértice 'b' tienen un borde conectado 'ab'. Entonces, con respecto al vértice 'a', solo hay un borde hacia el vértice 'b' y de manera similar con respecto al vértice 'b', solo hay un borde hacia el vértice 'a'. Finalmente, el vértice 'a' y el vértice 'b' tienen un grado que también se denomina vértice colgante.
Vértice aislado
Un vértice con grado cero se llama vértice aislado.
Example
Aquí, el vértice 'a' y el vértice 'b' no tienen conectividad entre sí y también con cualquier otro vértice. Entonces, el grado de ambos vértices 'a' y 'b' es cero. Estos también se denominan vértices aislados.
Proximidad
Aquí están las normas de adyacencia:
En un gráfico, se dice que dos vértices son adjacent, si hay una arista entre los dos vértices. Aquí, la adyacencia de los vértices se mantiene mediante el único borde que conecta esos dos vértices.
En un gráfico, se dice que dos bordes son adyacentes, si hay un vértice común entre los dos bordes. Aquí, la adyacencia de los bordes se mantiene mediante el único vértice que conecta dos bordes.
Example 1
En el gráfico anterior:
'a' y 'b' son los vértices adyacentes, ya que hay un borde común 'ab' entre ellos.
'a' y 'd' son los vértices adyacentes, ya que hay un borde común 'ad' entre ellos.
ab 'y' be 'son los bordes adyacentes, ya que hay un vértice común' b 'entre ellos.
be 'y' de 'son los bordes adyacentes, ya que hay un vértice común' e 'entre ellos.
Example 2
En el gráfico anterior:
'a' y 'd' son los vértices adyacentes, ya que hay un borde común 'ad' entre ellos.
'c' y 'b' son los vértices adyacentes, ya que hay un borde común 'cb' entre ellos.
'ad' y 'cd' son los bordes adyacentes, ya que hay un vértice común 'd' entre ellos.
'ac' y 'cd' son los bordes adyacentes, ya que hay un vértice común 'c' entre ellos.
Bordes paralelos
En un gráfico, si un par de vértices está conectado por más de una arista, esas aristas se denominan aristas paralelas.
En el gráfico anterior, 'a' y 'b' son los dos vértices que están conectados por dos aristas 'ab' y 'ab' entre ellos. Por eso se le llama como borde paralelo.
Multi Graph
Un gráfico que tiene bordes paralelos se conoce como Multigraph.
Example 1
En el gráfico anterior, hay cinco aristas 'ab', 'ac', 'cd', 'cd' y 'bd'. Dado que 'c' y 'd' tienen dos bordes paralelos entre ellos, es un Multigraph.
Example 2
En el gráfico anterior, los vértices 'b' y 'c' tienen dos aristas. Los vértices 'e' y 'd' también tienen dos aristas entre ellos. Por tanto, es un Multigraph.
Secuencia de grados de un gráfico
Si los grados de todos los vértices de un gráfico están dispuestos en orden descendente o ascendente, la secuencia obtenida se conoce como secuencia de grados del gráfico.
Example 1
| Vértice | UN | segundo | C | re | mi |
|---|---|---|---|---|---|
| Conectado a | antes de Cristo | anuncio | anuncio | c, b, e | re |
| La licenciatura | 2 | 2 | 2 | 3 | 1 |
En el gráfico anterior, para los vértices {d, a, b, c, e}, la secuencia de grados es {3, 2, 2, 2, 1}.
Example 2
| Vértice | UN | segundo | C | re | mi | F |
|---|---|---|---|---|---|---|
| Conectado a | ser | C.A | b, d | c, e | anuncio | - |
| La licenciatura | 2 | 2 | 2 | 2 | 2 | 0 |
En el gráfico anterior, para los vértices {a, b, c, d, e, f}, la secuencia de grados es {2, 2, 2, 2, 2, 0}.