Hola
Tengo estas 2 dudas de este nuevo tema de teoría de grados.
En el primer ejercicio, no entiendo por qué razón es imposible construir un grafo así. Creo que puede que la cosa vaya porque necesita ser conexo un grafo hamiltoniano, pero no sé..
Para que un grafo bipartitio sea hamiltoniano, tiene que tener un número para de vértices. Observa que el ciclo hamiltoniano que una todos los vértices debería de ir alternando vértices de un conjunto de la partición con vértices de la otro conjunto; por tanto los dos conjuntos en que ser particionan los vértices (por ser bipartito) deberían de tener el mismo número de vértices.
Respecto al segundo ejercicio esque no tengo ni idea, sinceramente.. Tengo las soluciones, pero me he quedado igual.
\( \left |{V_n}\right | = \displaystyle\frac{1}{2} 2^n \) No entiendo de donde sale el \( 1/2 \)
Los vértices son el número de cadenas de \( n \) bits on un número para de unos. Nota que hay tantas cadenas con número para de unos como con número impar, ya que cambiando el último bit (de cero a uno o de uno a cero) se transforma una cadena con un número pare de unos en una con número impar y viciversa. El número total de cadenas de \( n \) bits es \( 2^n \) (dos posibilidades para cada bit). Ya lo tienes.
Otra forma de verlo es tener en cuenta que el número de cadenas de \( n \) bits con un número pare de unos, es el número de subconjuntos con cardinal par del conjunto \( \{1,2,\ldots,n\} \) (los elementos de cada subconjunto indican en que posición están los unos). Puedes mirar entonces el problema (7) de aquí:
http://caminos.udc.es/info/asignaturas/101/pdfs/10_p02NOHECHO.pdfEl grado de los vértices \( d(v) = \displaystyle\binom{n}{2} \),
Cada vértice se une con una arista con otro que difiere exactamente en dos bits. Para contar cuantas cadenas difieren de una dada en dos bits, simplemente hay que contar las distintas posiciones en que pueden estar los dos bits diferentes. Es decir las formas de elegir dos posciones entre \( n \) totales: combinaciones de \( n \) elementos tomados de dos en dos.
Ten en cuenta además que si una cadena tiene un número par de unos, cualquiera que difiera de ella en dos bits también tiene un número par de unos.
Respecto a la última pregunta, primero tengo apuntado que habría que demostrar para que valores de n es conexo, y no entiendo la manera para saberlo. Y luego tengo apuntado esto de clase, que la verdad que me suena todo a chino...:
\( d=\displaystyle\binom{n}{2}=2p \Rightarrow{} n(n-1) = 4p \Rightarrow{}n=4q; n=4q+1 \), para esos valores de n, es euleriano.
El grafo siempre es conexo. Cualquier vértice está unido con el vértice correspondiente a una cadena de ceros; ya que cualquier cadena de bits con un número para de unos puede transformase en "todo ceros" en varios pasos, cambiando en cada paso dos unos por dos ceros.
Por otra parte un grafo conexo es euleriano si y sólo si cada vértice tiene grado par. En nuestro caso si y sólo si \( \binom{n}{2} \) es par, es decir,
\( \dfrac{n(n-1)}{2}=2p \)
Equivalentemente si:
\( n(n-1)=4p \)
es decir si \( n \) ó \( n-1 \) es múltiplo de cuatro.
Saludos.
