Wie kommt man auf das Maximum Matching?

 - (Computer, Technik, Technologie)  - (Computer, Technik, Technologie)

1 Antwort

Da der Graph klein ist, kannst Du es durchprobieren, das maximale Matching kann nicht größer als 6 werden.

Andernfalls lies mal:

https://de.wikipedia.org/wiki/Matching_(Graphentheorie)#L%C3%B6sungsverfahren

Guten Morgen.

Ok dann muss ich aber fragen, warum man hier nicht einfach die gegenüberliegenden Knoten verbunden, hat, damit hätte man 6 Matchings bekommen. Ich glaube ich habe die Definition dann doch nicht verstanden, denn es macht keinen Sinn für mich, warum man diese Kanten so einzeichnet.

In einem Matching müssen doch alle Kanten untereinander Knotendisjukt sein?

0

Achso es gibt verschiedene maximale Matchings ?

z.B

a1->b3 , a2->b4, a3-> b2 , a4->b1, a6->b6 ?

0
@Svenja1565

Japp, ebenso ginge die Diagonalen zu nehmen, also beginnend mit a6->b5 und dann eben nach unten. (a1 und b6 sind dann eben außen vor)

0

Was möchtest Du wissen?