En un gráfico no dirigido, ¿cuál es el grado de un vértice con un bucle automático?

Según Introducción a los algoritmos (página 1169 de la tercera edición, por ejemplo): “En un gráfico no dirigido, los bucles automáticos están prohibidos, por lo que cada borde consta de dos vértices distintos”. Por lo tanto, si utiliza nuestra definición de un no dirigido gráfico, la pregunta es discutible. ¿Qué fuente usa su clase que permite que los gráficos no dirigidos tengan bucles automáticos?

Eso depende. No hay una única respuesta correcta. Debe usar la versión que realmente tenga sentido en su caso particular.

La respuesta más común será 2, porque es más consistente con el caso general. Cada borde tiene dos extremos, por lo tanto, la suma de los grados de vértice es el doble del número total de bordes. Esta es una buena propiedad, y decir que un autociclo aumenta el grado de su vértice en 2 conserva esta propiedad. (Puede ver esto de la siguiente manera: “cada vez que estoy dibujando un nuevo borde, incremento el grado del vértice donde comienzo, luego dibujo el borde y luego incremento el grado del vértice que acabo de alcanzar”).

Sin embargo, también hay casos en los que la otra opción tiene más sentido. Digamos que estoy usando un gráfico no dirigido para modelar cómo una persona explora una ciudad. Los bordes representan sus posibles acciones durante cada minuto: pueden moverse a una ubicación adyacente o pueden permanecer en su ubicación actual. En esta configuración, es más conveniente decir que un autociclo contribuye solo 1 al grado de su vértice. Luego, el grado del vértice representa la cantidad de opciones que la persona puede elegir.

En “Matemáticas discretas y sus aplicaciones” de Kenneth H Rosen, séptima edición dice: “el grado de un vértice en un gráfico no dirigido es el número de bordes incidentes en él, excepto que un bucle en un vértice contribuye dos veces al grado de ese vértice”

Realmente depende de usted, cómo lo cuenta. Contar como 2 tiene la ventaja de crear el bucle de varios teoremas en menos casos. Muchos teoremas en la teoría de grafos no funcionan en gráficos con bucle automático, y muchos teoremas sí. Si cuenta el grado como 1, entonces funcionarían menos teoremas en gráficos con auto-loop.

Como ejemplo, la fórmula de Euler. v-e + f = 2 en gráficos planos. Si cuenta el ciclo automático como grado 2, entonces esta fórmula también es aplicable con gráficos en ciclo automático.

Gráfico plano

Para un gráfico no dirigido, el grado de vértice se puede calcular mediante el método habitual, que es 1 por cada borde que incide en el gráfico, aquí la única excepción es cómo contamos la contribución al grado mediante bucles automáticos para un bucle automático de gráfico que contribuye con un grado de 2.

Tomemos un ejemplo

En el ejemplo anterior, el grado de vértice etiquetado 5 se calcula como 1 + 1 + 1 + 2 = 5.

Gracias por leer :).

Piense esto ya que cada borde tiene 2 grados. Si un borde está entre dos vértices, ambos vértices tienen un grado de uno. Ahora vea que el bucle de borde vuelve a sí mismo, así es como un bucle tiene dos grados. el grado no depende del vértice sino de los bordes.

Su profesor tiene razón, un vértice enrollado sobre sí mismo es un caso especial y tiene un grado de 2.
Como nos referimos a gráficos no dirigidos, necesitamos contar el borde desde ambos extremos. (Piense que tiene dos formas de alcanzar el vértice sobre el mismo borde (el bucle en cuestión)).