Autor |
Mensaje |
fede03
Nivel 5
Edad: 32
Registrado: 28 Jul 2010
Mensajes: 149
Ubicación: Escobar y San Cristobal
Carrera: Sistemas
|
|
Aca dejo una demostración que la estuve viendo con un amigo pero no salió jaja. Si alguien puede contribuir algo, bienvenido sea!
- Si G es un grafo no conexo y A=V-1 entonces G es aciclico.
|
|
|
|
_________________ Fedee ! - "Más que una carrera, una caminata universitaria".
|
|
|
|
|
Ajax08
Nivel 5
Registrado: 30 Dic 2008
Mensajes: 168
|
|
Es FALSA la proposición. El contraejemplo sería:
Grafo G de 3 vértices en los cuales una arista une 2 vértices y un bucle en el tercer vértice.
Con esto se obtienen dos componentes conexas, una con dos vértices y una arista y otra con un vértice y una arista (o sea G no es conexo). Además se cumple que 2 aristas = 3 Vértices - 1 (CON ESTO : HIPOTESIS VERDADERA).
Pero la tesis es FALSA ya que hay un bucle y por lo tanto no es acíclico.
En el enunciado del ejercicio dice analizar el valor de verdad de la proposición, asi que es Falsa.
|
|
|
|
|
|
|
|
|
Pastore
Nivel 6
Registrado: 06 Ene 2009
Mensajes: 283
Carrera: Informática
|
|
Ya que estamos, alguien sabe como justificar esta:
La cantidad de vertices de grados impar de un grafo, es par
|
|
|
|
|
|
|
|
|
fede03
Nivel 5
Edad: 32
Registrado: 28 Jul 2010
Mensajes: 149
Ubicación: Escobar y San Cristobal
Carrera: Sistemas
|
|
Ajax08 escribió:
|
Es FALSA la proposición. El contraejemplo sería:
Grafo G de 3 vértices en los cuales una arista une 2 vértices y un bucle en el tercer vértice.
Con esto se obtienen dos componentes conexas, una con dos vértices y una arista y otra con un vértice y una arista (o sea G no es conexo). Además se cumple que 2 aristas = 3 Vértices - 1 (CON ESTO : HIPOTESIS VERDADERA).
Pero la tesis es FALSA ya que hay un bucle y por lo tanto no es acíclico.
En el enunciado del ejercicio dice analizar el valor de verdad de la proposición, asi que es Falsa.
|
Muchas gracias Ajax!
Pastore masomenos es asi.
Supongo el conjunto V formado por {V1,V2,...,Vk ; W1,W2,...,Wk} con V siendo los grados pares y W siendo los grados impares del grafo.
Con la formula de sumatoria (sumatoria de todos los grados del grafo = 2 . |A|) deducis lo siguiente:
Sumatoria gr(Vi) + Sumatoria gr(Wi) = 2 . |A|
=PAR =PAR
Entonces te quedaria Sumatoria de Wk = PAR
Y esto de la unica forma que se da es que vayas juntando de a 2 los vertices de grado impar asi cuando sumas, te queda un resultado par. Siempre vas a tener pares de impares.
Creo que algo asi es, por lo menos es lo que yo entendi. Espero que te sirva y sino que alguien aporte algo mas
|
|
|
|
_________________ Fedee ! - "Más que una carrera, una caminata universitaria".
|
|
|
|
|
fede03
Nivel 5
Edad: 32
Registrado: 28 Jul 2010
Mensajes: 149
Ubicación: Escobar y San Cristobal
Carrera: Sistemas
|
|
EDIT: Salio mal
(...)
Sumatoria gr(Vi) + Sumatoria gr(Wi) = 2 . |A|
.......=PAR..........................................=PAR
(Ya que al sumar todos los grados par, te va a dar un numero par y siempre 2 por algo, es un numero par)
Entonces te quedaria Sumatoria de gr(Wi) = PAR
(...)
|
|
|
|
_________________ Fedee ! - "Más que una carrera, una caminata universitaria".
|
|
|
|
|
fede03
Nivel 5
Edad: 32
Registrado: 28 Jul 2010
Mensajes: 149
Ubicación: Escobar y San Cristobal
Carrera: Sistemas
|
|
Dejo otra demostracion que la verdad no tengo idea por donde empezar.
- Probar que para todo a perteneciente a una algebra de boole se tiene: a distinto de ~a(complemento).
Muchas gracias!
|
|
|
|
_________________ Fedee ! - "Más que una carrera, una caminata universitaria".
|
|
|
|
|
gedefet
Nivel 9
Edad: 34
Registrado: 06 May 2008
Mensajes: 936
Carrera: Electrónica
|
|
Mirá la verdad que me acuerdo muy poco los axiomas, pero podrías suponer que son iguales, y luego llegar a un absurdo. Por ejemplo:
a=-a
aa=(-a)a=0-->a=0
a=-a
a+a=-a+a=1-->a=1
Capaz mandé fruta, pero por ahí debe andar. Saludos
|
|
|
|
_________________ Problemas con matemática? Llamá gratis al 0-800-3x²±sen(1/n³)∫∆ƒ dx
|
|
|
|
|
fede03
Nivel 5
Edad: 32
Registrado: 28 Jul 2010
Mensajes: 149
Ubicación: Escobar y San Cristobal
Carrera: Sistemas
|
|
Muchas gracias! Si, debe andar por ahi la solución
|
|
|
|
_________________ Fedee ! - "Más que una carrera, una caminata universitaria".
|
|
|
|
|
|