Autor Tema: Número de aristas de un grafo r-regular y de L(G)

0 Usuarios y 1 Visitante están viendo este tema.

18 Noviembre, 2019, 05:05 am
Leído 868 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Determine el número de aristas de un grafo \( r \)-regular con \( n \) vértices y del grafo de línea de un grafo \( G. \)

Hola, en ambos casos no es \( \dfrac{n(n-1)}{2} \)?
"Haz de las Matemáticas tu pasión".

18 Noviembre, 2019, 10:24 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Determine el número de aristas de un grafo \( r \)-regular con \( n \) vértices y del grafo de línea de un grafo \( G. \)

Hola, en ambos casos no es \( \dfrac{n(n-1)}{2} \)?

No.

Recuerda que:

\( m=\dfrac{1}{2}\displaystyle\sum_{v\in V}deg(v) \)

En un grafo \( r \)-regular todos los vértices tienen grado \( r \). Usando la fórmula anterior, si tenemos \( n \) vértices el número de aristas es....

En cuanto al grafo de línea \( L(G) \) de un grafo \( G \) es aquel cuyos vértices son las aristas de \( G \) y se consideran anexas aquellas que tienen un vértice común. De esta forma cara arista de \( L(G) \) corresponde a dos aristas \( e,e' \) con un vértice común que queda determinado de manera inequívoca como \( e\cap e'. \)

Entonces por cada vértice \( v\in G \), hay tantas aristas de \( L(G) \) que se intersecan en \( v \), como pares de vértices distintos anexos a \( v. \) Si \( v \) tiene grado \( deg(G) \) hay \( \displaystyle\binom{deg_G(v)}{2} \) formas de emparejar esos vértices. Por tanto el número de aristas de \( L(G) \) es:

\( \displaystyle\sum_{v\in V(G)}\displaystyle\binom{deg_G(v)}{2} \)

Saludos.