20/11/2019, 09:23:56 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: ¡Atención! Hay que poner la matemática con LaTeX, y se hace así (clic aquí):
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Demostrar que no existe un grafo bipartito con \(7\) vértices y \(13\) aristas  (Leído 98 veces)
0 Usuarios y 1 Visitante están viendo este tema.
manooooh
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 2.386


Ver Perfil
« : 10/11/2019, 09:41:48 pm »

Hola!!

Dibujar un grafo que cumpla lo siguiente. En caso de no ser posible justificar:

Un grafo bipartito con siete vértices y trece aristas.



Mi profesor lo justifica así:

No se puede ya que el bipartito completo [texx]K_{4,3}[/texx] tiene [texx]12[/texx] aristas, el [texx]K_{5,2}[/texx] tiene [texx]10[/texx] y el [texx]K_{6,1}[/texx] tiene [texx]6[/texx]. Como los [texx]K_{n,m}[/texx] son simples, no pueden tener [texx]13[/texx] aristas y [texx]7[/texx] vértices.



Yo veo que la demostración es pobre. Lo justificaría así:

Sabemos que si [texx]K_{n,m}[/texx] es un grafo bipartito completo entonces [texx]|V|=n+m[/texx] y [texx]|A|=n\cdot m[/texx]. Hallar tal grafo equivale a resolver el siguiente sistema de ecuaciones: \[\left\lbrace\begin{aligned}&n+m=7\\&n\cdot m=13\end{aligned}\right.\] Como la solución no es entera concluimos que no es posible hallar tal grafo.



Sin embargo no sé por qué mi profesor y yo hablamos de GRAFOS BIPARTITOS COMPLETOS cuando el enunciado sólo habla de GRAFO BIPARTITO. El grafo bipartito completo se lo denota [texx]K_{n,m}[/texx] pero el bipartito a secas no es así :¿eh?:.

Gracias!!
Saludos
En línea
Richard R Richard
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 85



Ver Perfil
« Respuesta #1 : 10/11/2019, 11:36:24 pm »

 Hola e presento mi forma rudimentaria de verlo

Si [texx]n, m \in N[/texx] y [texx]n+m=7[/texx] suponiendo que el grafo es completo  que cada elemento [texx]n_i[/texx] se una con uno de [texx]m_j[/texx] podria hallar el máximo de aristas con [texx]n.m[/texx]

[texx]a_{ristas}=n.m=n.(7-n)[/texx]

Un máximo lo tienes cuando

[texx]\dfrac{\partial a_{ristas}}{\partial n}=0[/texx]

 que te llevaría a [texx]n=3.5[/texx] si fuera posible elegir racionales , pero solo puedes elegir los enteros mas cercanos,  en este caso 3 y 4  , para el caso es lo mismo si [texx]m=3[/texx] o [texx]n=3[/texx] porque  [texx]n.m= 12[/texx] y es el máximo , por lo que  nunca llega a 13,  luego es imposible ese grafo bipartito....

y si... entiendo que si el grafo bipartito es completo tiene que cumplirse que

[texx]\left\lbrace\begin{aligned}&n+m=V_{ertices}\\&n\cdot m=A_{ristas}\end{aligned}\right.\quad \forall n,m \in \mathbb N \color{red}{|n\geqslant 1 \wedge m\geqslant 1}\color{black}[/texx]


si el grafo es bipartito y no completo

[texx]\left\lbrace\begin{aligned}&n+m=V_{ertices}\\&n\cdot m\geqslant A_{ristas}\end{aligned}\right.\quad \forall n,m \in \mathbb N \color{red}{|n\geqslant 1 \wedge m\geqslant 1}\color{black}[/texx]

fijate que con 8 vértices  si puedes dibujar 13 aristas, con 4 y 4 vertices y tambien con 5 y 3 o bien 3 y 5 ,pero puedes también dibujar 16 o 15 aristas respectivamente si lo quieres completo.

Innecesario por la propia definición de número natural.
En línea

Saludos  \(\mathbb {R}^3\)
martiniano
Pleno*
*****

Karma: +2/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 932


Ver Perfil
« Respuesta #2 : 11/11/2019, 03:39:45 am »

Hola.

Sin embargo no sé por qué mi profesor y yo hablamos de GRAFOS BIPARTITOS COMPLETOS cuando el enunciado sólo habla de GRAFO BIPARTITO. El grafo bipartito completo se lo denota [texx]K_{n,m}[/texx] pero el bipartito a secas no es así :¿eh?:.

Es que cualquier grafo bipartito con siete vértices lo puedes construir quitando aristas de uno de los completos que da tu profe. Al tener todos ellos menos de trece aristas no existe un grafo como el del enunciado.

Tu respuesta no está completa. Fíjate que habrías llegado a la misma conclusión si fuesen 11 aristas. Sin embargo, quitando una arista de [texx]K_{4,3} [/texx] lo tendrías.

Un saludo.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 45.421


Ver Perfil
« Respuesta #3 : 11/11/2019, 04:24:52 am »

Hola

Sin embargo no sé por qué mi profesor y yo hablamos de GRAFOS BIPARTITOS COMPLETOS cuando el enunciado sólo habla de GRAFO BIPARTITO. El grafo bipartito completo se lo denota [texx]K_{n,m}[/texx] pero el bipartito a secas no es así :¿eh?:.

Por completar lo que te ha dicho martiniano, es que tu profesor habla de grafo bipartito completo de manera auxiliar. Para ver cual es el máximo número de aristas que puede tener un grafo bipartito (no necesariamente completo) de [texx]7[/texx] vértices. Como dice martiniano cualquier grafo bipartitio se puede completar a uno completo añadiendo aristas.

Saludos.
En línea
manooooh
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 2.386


Ver Perfil
« Respuesta #4 : 12/11/2019, 09:14:57 pm »

Hola

No entiendo cómo se sabe que el único grafo bipartito que "tiene como máximo número de aristas" puede ser el [texx]K_{4,3}[/texx] (o el [texx]K_{3,4}[/texx], es irrelevante). ¿Se puede demostrar matemáticamente que cualquier otro grafo bipartito con [texx]7[/texx] vértices necesariamente ha de tener menor número de aristas que el [texx]K_{4,3}[/texx] o sea menor que [texx]12[/texx]?

Y de ahí arribamos a que es imposible que haya uno de [texx]13[/texx]. Pero no veo que se haya demostrado que como máximo pueden haber [texx]12[/texx], porque el nombrar los casos me parece insuficiente (unos cuantos casos no dicen nada acerca de la veracidad o falsedad de algo aunque puede dar algún indicio, no constituye una prueba formal). Y si me dicen "Pero oye, todos los casos posibles son los que dio tu profesor más los "simétricos"" entonces para mí no sigue constituyendo una prueba formal.

Gracias y saludos
En línea
Richard R Richard
Semi pleno
***

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 85



Ver Perfil
« Respuesta #5 : 13/11/2019, 12:05:59 am »

Mi opinión, si te sirve, un grafo bipartito tiene el máximo número de aristas cuando los números de vértices cumplen [texx]n\cong m[/texx] es decir cuando el número de aristas tiende [texx]\cong n^2\cong\left[ \dfrac{V_{ertices}}2\right]^2[/texx] mas precisamente  podrías demostrar que cualquier grafo bipartito cumple

[texx]V_{ertices\,Max} PAR|n=m\Longrightarrow{} A_{ristas }\leqslant n^2=\left[ \dfrac{V_{ertices}}2\right]^2[/texx]

y si [texx]V_{ertices\,Max} IMPAR| V_{ertices}=2n-1| n=m+1\Longrightarrow{} A_{ristas }\leqslant n^2-n=nm[/texx]
En línea

Saludos  \(\mathbb {R}^3\)
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 45.421


Ver Perfil
« Respuesta #6 : 13/11/2019, 05:50:36 am »

Hola

No entiendo cómo se sabe que el único grafo bipartito que "tiene como máximo número de aristas" puede ser el [texx]K_{4,3}[/texx] (o el [texx]K_{3,4}[/texx], es irrelevante). ¿Se puede demostrar matemáticamente que cualquier otro grafo bipartito con [texx]7[/texx] vértices necesariamente ha de tener menor número de aristas que el [texx]K_{4,3}[/texx] o sea menor que [texx]12[/texx]?

El resumen del argumento que usa tu profesor es:

1) Un grafo bipartito tiene dividido los vértices en dos subconjuntos disjuntos no vacíos y las aristas sólo pueden unir vértices de un subconjunto con vértices del otro.

2) Si tenemos [texx]7[/texx] vértices las posibilidades para dividir en dos grupos los vértices son:

- Uno de [texx]6[/texx] y otro de [texx]1[/texx].
- Uno de [texx]5[/texx] y otro de [texx]2[/texx].
- Uno de [texx]4[/texx] y otro de [texx]3[/texx].

3) El conjunto de aristas de cualquier grafo bipartito en una partición de vértices [texx]U,V[/texx] es un subconjunto de aristas del grafo bipartito completo con esa misma partición, ya que las aristas del grafo bipartito sólo unen vértices de [texx]U[/texx] con vértices de [texx]V[/texx] y el completo toma TODAS esas aristas.

4) Por (3) si [texx]G[/texx] es un grafo bipartito con partición de vértices [texx]U,V[/texx], [texx]n=card(U)[/texx] y [texx]m=card(V)[/texx] se cumple que:

[texx]\textsf{nº aristas}(G)\leq \textsf{nº aristas}(K_{n,m})=nm[/texx]

5) Por (2) y (4) un grafo bipartito de [texx]7[/texx] aristas cumple una de las siguientes desigualdades:

[texx]\textsf{nº aristas}(G)\leq 6\cdot 1=6[/texx]
[texx]\textsf{nº aristas}(G)\leq 5\cdot 2=10[/texx]
[texx]\textsf{nº aristas}(G)\leq 4\cdot 3=12[/texx]

y por tanto [texx]\textsf{nº aristas}(G)\leq max\{6,10,12\}=12[/texx].

Cita
Y de ahí arribamos a que es imposible que haya uno de [texx]13[/texx]. Pero no veo que se haya demostrado que como máximo pueden haber [texx]12[/texx], porque el nombrar los casos me parece insuficiente (unos cuantos casos no dicen nada acerca de la veracidad o falsedad de algo aunque puede dar algún indicio, no constituye una prueba formal). Y si me dicen "Pero oye, todos los casos posibles son los que dio tu profesor más los "simétricos"" entonces para mí no sigue constituyendo una prueba formal.

Es que no son "unos cuantos casos" son TODOS los casos los que se han explorado.

Saludos.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!