Diskrete Strukturen: Fragen

Erfahrener Schreiberling

Date of registration: Oct 14th 2002

Sunday, June 15th 2008, 11:33am

Hi, ich arbeite gerade ein paar Übungsblätter zu Diskrete Strukturen auf und habe ein Problem bei Blatt 5: Ist G2 hamiltonsch ?

Esi ist die Matrix gegeben:

	Source code
1 2 3 4 5 6 7 8	0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 0

Angeblich existiert ein Hamiltonkreis. Aber woher weiß ich das ?

Weder alle Knotengrade > |V|/2
noch deg(x)+deg(y) >= |V| für alle x!=y, {x,y} nicht in E

Oder doch? Wer weiß mehr. danke.

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Sunday, June 15th 2008, 1:23pm

RE: Diskrete Strukturen: Fragen

Quoted from "Currywurst mit Pommes"
Source code
1
2
3
4
5
6
7
8
0 1 0 1 0 0 1 0
1 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0
1 0 1 0 1 0 0 1
0 0 0 1 0 1 0 1
0 0 0 0 1 0 1 0
0 1 0 0 0 1 0 1
0 0 0 1 1 0 1 0
Angeblich existiert ein Hamiltonkreis. Aber woher weiß ich das ?

Den Graph aufmalen auf "scharf hingucken" (allzuviel Schärfe ist hier nicht erforderlich). Die von Dir genannten Bedingungen sind nur hinreichend für einen Hamiltonkreis. Das allgemeine Problem (also für beliebige Graphen festzustellen, ob dieses einen Hamiltonkreis besitzen) ist ja NP-vollständig, im großen und ganzen also wohl nur durch Durchprobieren aller möglichen Pfade zu lösen.

The purpose of computing is insight, not numbers.

– Richard Hamming, 1962

Go to the top of the page

Currywurst mit Pommes

Erfahrener Schreiberling

Posts: 438

Date of registration: Oct 14th 2002

3

Sunday, June 15th 2008, 3:23pm

Alles klar. Also wurde hier wohl erwartet, dass "scharf hingesehen" bzw. gezeichnet wird. Hatte vermutet, dass wir das nur anhand der Sätze erkennen brauchen.

Go to the top of the page

Currywurst mit Pommes

Erfahrener Schreiberling

Posts: 438

Date of registration: Oct 14th 2002

4

Monday, July 14th 2008, 10:14pm

Weiß jemand noch den Lösungsweg für eine Aufgabe aus Blatt 2 ?

Vier Ehepaare nehmen an einem Tanzkurs teil. Bei wievielen der 24 verschiedenen
Tanzkonstellationen tanzt kein Ehepaar miteinander?

Lösung: 9 - aber wie ?

Go to the top of the page

CrissCross

Erfahrener Schreiberling

Posts: 282

Date of registration: Feb 15th 2005

5

Monday, July 14th 2008, 11:21pm

Quoted from "Currywurst mit Pommes"

Weiß jemand noch den Lösungsweg für eine Aufgabe aus Blatt 2 ?

Vier Ehepaare nehmen an einem Tanzkurs teil. Bei wievielen der 24 verschiedenen
Tanzkonstellationen tanzt kein Ehepaar miteinander?

Lösung: 9 - aber wie ?

Ich schätze mal, dass die so gerechnet haben, dass die 4 Ehepaare auf 4 Tanzpaare verteilt haben. Und zwar (was ja beim Tanzkurs irgendwie gar keinen Sinn macht) mit Berücksichtigung der Startreihenfolge: Also 4! = 24.
Ich kann jetzt nur schätzen, wie das gemeint ist, dass "kein Ehepaar" miteinander tanzt: Gemeint ist vielleicht, dass niemand neben seinem Ehepartner steht. Weder im selben Paar (Also -4 : Die ursprünglichen Ehepaare), noch in dem Fall, wenn die Paare nebeneinander stehen. Also, dass praktisch eine Konstellation wie (Mann1, Frau2), (Mann2, Frau1) auch nicht erlaubt ist.

"Technology is easy - people are hard."

(John Gage - Sun Microsystems zum Thema warum IT-Projekte scheitern)

Go to the top of the page

snoopy

Junior Schreiberling

Posts: 146

Date of registration: Feb 29th 2004

Location: Hannover

Occupation: Informatik

6

Tuesday, July 15th 2008, 12:34am

Die 9 ist doch ganz einfach. Findest Du durch Aufschreiben und Streichen aller Permutationen. Geht sicher auch mathematischer. Du hast vier Paare und stellt z.B. die 4 Kerle hin und verteilst dann die Mädels so, dass kein Paar zusammen tanzt. In Zahlen: Schreibe alle Permuationen der Zahlen 1 bis 4 in 4 Spalten nebeneinander auf. Streichen alle Zeilen auf in der in der nten Spalte die Zahl n steht.

9 ist die Anzahl der Permutationen einer 4-elementigen Menge ohne Fixpunkte.
(2 1 4 3)
(2 3 4 1)
(2 4 1 3)
(3 1 4 2)
(3 4 1 2)
(3 4 2 1)
(4 1 2 3)
(4 3 2 1)
(4 3 1 2)

This post has been edited 2 times, last edit by "snoopy" (Jul 15th 2008, 12:37am)

Go to the top of the page

Schokoholic

Fritz

Posts: 2,518

Date of registration: Oct 4th 2006

Location: Hannover

Occupation: Haarspaltung

7

Tuesday, July 15th 2008, 12:44am

Genau. Snoopy war schneller.

Wer die Formel dafür wissen möchte, eine fixpunktfreie Permutation heißt auch Derangement: http://de.wikipedia.org/wiki/Derangement

EDIT: Wir haben ja nun LaTeX hier

Quoted from "Wikipedia"

Die Anzahl der möglichen Derangements einer Menge mit Elementen entspricht der Subfakultät :
$\Large d_n = !n = n! \cdot \sum_{i=0}^n {\left(-1\right)^i \over i!}$ .