Autor Tema: Grafo bipartito y aplicaciones inyectivas

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

14 Mayo, 2022, 05:23 pm
Leído 64 veces

Pacomg

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 4
  • Karma: +0/-0
  • Sexo: Masculino
Buenas tardes
Tengo un problema que le estoy dando vueltas y no sé si la utilización de grafos me llevará a una solución.
Tengo un grafo bipartito con 20 vértices, 10 en cada grupo y todos de orden 3.
Lo que me preguntó si hay alguna forma de demostrar si existe una aplicación inyectiva entre el primer grupo de vértices y el segundo utilizando 10 aristas del grafo.
Y la misma pregunta cuando el primer grupo tiene 10 vértices y el segundo tiene 15 y todos los vértices tienen orden 3.
A fuerza bruta encuentro una aplicación inyectiva para cada caso. Pero la pregunta es si habrá relación con encontrar un camino hamiltoniano, alguna coloración de aristas, ..... en el grafo.
El origen del problema es que tenemos dos conjuntos y partimos de una relación entre los elementos de cada conjunto y asi se obtiene el grafo bipartito anterior, según el número de elementos de cada conjunto. Lo que se pide es encontrar una aplicación inyectiva, que como ya he dicho la he encontrado, pero quiero ver si existe esa relación por la que pregunto.
Gracias
saludos