eXtra zadanie - tylko dla orłów?

Jednym z zadań trwającego obecnie Mistrzostw w Grach Matematycznych i Logicznych sformułowane zostało następujące zadanie: (patrz zadanie 14):

Problem

W grupie złożonej z N osób (gdzie N = 16) każda osoba ma dokładnie trzech znajomych w tej grupie. Czy zawsze można wszystkie osoby z tej grupy ustawić parami tak, aby w każdej parze znalazły się osoby, które się znają ?

Zakładamy, że relacja znajomości jest symetryczna, tzn. że jeśli osoba A zna osobę B, to również B zna A.

Zadanie programistyczne

Napisz program rozwiązujący Problem dla dowolnego parzystego N > 2.

Program powinien przeszukiwać wszelkie możliwe grafy powiązań N osób więzami znajomości, w których każda z osób zna dokładnie 3 inne.

Po znalezieniu każdego takiego grafu program winien sprawdzić, czy da się w nim połączyć osoby w pary.

Jeśli uda się znaleźć taki graf, to program powinien go wydrukować.

Jeśli nie istnieje taki graf, to program powinien o tym poinformować po zakończeniu generowania wszelkich możliwych grafów.

Dla wygody testowania program powinien umożliwiać wydruki kolejno wygenerowanych grafów znajomości oraz znalezionego ustawienia w pary.

Termin składania rozwiązań

Samodzielnie stowrzone programy oceniane będą do dnia egzaminu włącznie.

Kryteria oceny rozwiązań

Podane w kolejności od najbardziej, do najmniej znaczących:
  1. Poprawność
  2. Elegancja, np. w kwestii doboru struktur danych użytych do reprezentacji danych, doboru algorytmów, etc.
  3. Szybkość działania

Komentarz

Zadanie uważam za trudne. Łatwiej będzie, moim zdaniem, zaliczyć ćwiczenia i nauczyć się wykładanego matriału, niż stworzyć satysfakcjonujący program. Tym niemniej, namawiam wszystkich do spróbowania swoich sił. Powodzenia!
Kontakt: IPI PAN
e-mail: m.bednarczyk@ipipan.gda.pl
s-mail: Instytut Podstaw Informatyki, filia Gdańsk, Abrahama 18, 81-825 Sopot
Powered by APACHE