Uczę się na egzamin poprawkowy z przedmiotu "Matematyka Dyskretna 1". Na pierwszym terminie poległem (m.in.) na zadaniu o treści:
"Wyznacz liczbę zbiorów niezależnych w grafie:" graf to droga n-elementowa zakończona cyklem l-elementowym, tak, że przypomina to lizaka.
Nie potrafię tego ugryźć, a nie chciałbym znowu polec na tym zadaniu. Prosiłbym o pomoc, a przynajmniej o pchnięcie mnie w odpowiednim kierunku.
Z góry dziękuję za pomoc.
Ilość zbiorów niezależnych
-
miodzio1988
Ilość zbiorów niezależnych
Masz definicje. W czym jest problem? Wiesz co to jest cykl? Droga? Czy ta droga ma parzystą ma dlugość czy nieparzystą? Swoją drogą najpierw to na palcach mozna policzyc. I to Ci zalecam
Ilość zbiorów niezależnych
Teraz to już nic nie wiem.
Czy to zadanie jest tak proste, że aż trudne?
Czy może ja czegoś nie rozumiem?
Bo tak logicznie myśląc mógłbym napisać, że dwa (dla grafu z parzystą liczbą wierzchołków - z parzystymi i nie parzystymi wierzchołkami) lub trzy (dla grafu z nieparzystą liczbą wierzchołków - jeden z parzystymi i dwa z nieparzystymi - zależy od której strony zacząć wybierać). Jednak są to dane prosto z sufitu, niepoparte żadnym dowodem/wywodem/obliczeniami. Pisząc takie rozwiązanie dostałbym co najwyżej 1 punkt na 10 za poprawne rozwiązanie (chociaż pewnie z tymi odpowiedziami to się tutaj pomyliłem, bo myślałem o zbiorach maksymalnych)
Jeżeli to jest dobry tok rozumowania, to ja się chyba zastrzelę.
Jeśli jednak nie, to prosze o pomoc, bo nijak nie potrafie sie zorientować w tym.
PS. W pierwszym poście jest podana cała treść zadania. Opis grafu jest mój, zadany był rysunkiem. wykładowca żadnych dodatkowych informacji nie podał.
Czy to zadanie jest tak proste, że aż trudne?
Czy może ja czegoś nie rozumiem?
Bo tak logicznie myśląc mógłbym napisać, że dwa (dla grafu z parzystą liczbą wierzchołków - z parzystymi i nie parzystymi wierzchołkami) lub trzy (dla grafu z nieparzystą liczbą wierzchołków - jeden z parzystymi i dwa z nieparzystymi - zależy od której strony zacząć wybierać). Jednak są to dane prosto z sufitu, niepoparte żadnym dowodem/wywodem/obliczeniami. Pisząc takie rozwiązanie dostałbym co najwyżej 1 punkt na 10 za poprawne rozwiązanie (chociaż pewnie z tymi odpowiedziami to się tutaj pomyliłem, bo myślałem o zbiorach maksymalnych)
Jeżeli to jest dobry tok rozumowania, to ja się chyba zastrzelę.
Jeśli jednak nie, to prosze o pomoc, bo nijak nie potrafie sie zorientować w tym.
PS. W pierwszym poście jest podana cała treść zadania. Opis grafu jest mój, zadany był rysunkiem. wykładowca żadnych dodatkowych informacji nie podał.
-
miodzio1988
Ilość zbiorów niezależnych
Jak graf ma drogę \(\displaystyle{ n}\) elementową no to w tej drodze ma \(\displaystyle{ n}\) wierzcholkow, nie?
A jaka jest definicja drogi? Ktore wierzcholki w drodze sa zbiorem niezaleznym?
A jaka jest definicja drogi? Ktore wierzcholki w drodze sa zbiorem niezaleznym?
-
Dumel
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
Ilość zbiorów niezależnych
ide dopiero na pierwszy rok więc może użyta przeze mnie terminologia będzie niepoprawna, ale idea myśle że jest ok:
zrobiłem taki oto cudowny rysuneczek:
niech \(\displaystyle{ d_i}\) oznacza liczbę zbiorów niezależnych na drodze \(\displaystyle{ i}\)-wierzchołkowej (zakładam że zbiór niezawierający wierzchołków też jest zbiorem niezależnym). mamy \(\displaystyle{ d_0=1}\) i \(\displaystyle{ d_1=2}\) oraz \(\displaystyle{ d_{i+1}=d_i+d_{i-1}}\) - więc \(\displaystyle{ d_i=F_{i+1}}\) gdzie \(\displaystyle{ F_k}\) oznacza \(\displaystyle{ k}\)-tą liczbę Fibonacciego (jeśli potrzebujesz zwartego wzoru to Binet służy pomocą)
czerwony i różowy wierzchołek (z tego przecudnego rysunku) nie mogą jednocześnie należeć do zbioru niezależnego. trzy przypadki:
1. tylko czerwony należy- mamy \(\displaystyle{ d_{l-3}+d_n}\) takich zbiorów
2. tylko różowy należy - \(\displaystyle{ d_{n-1}+d_{l-3}}\)
3. żaden z nich nie należy do rozpatrywanego zbioru: \(\displaystyle{ d_{l-2}+d_n}\)
sumujemy, wykorzystujemy poprzednie spostrzeżenia i gotowe. wszystko jasne?
zrobiłem taki oto cudowny rysuneczek:
niech \(\displaystyle{ d_i}\) oznacza liczbę zbiorów niezależnych na drodze \(\displaystyle{ i}\)-wierzchołkowej (zakładam że zbiór niezawierający wierzchołków też jest zbiorem niezależnym). mamy \(\displaystyle{ d_0=1}\) i \(\displaystyle{ d_1=2}\) oraz \(\displaystyle{ d_{i+1}=d_i+d_{i-1}}\) - więc \(\displaystyle{ d_i=F_{i+1}}\) gdzie \(\displaystyle{ F_k}\) oznacza \(\displaystyle{ k}\)-tą liczbę Fibonacciego (jeśli potrzebujesz zwartego wzoru to Binet służy pomocą)
czerwony i różowy wierzchołek (z tego przecudnego rysunku) nie mogą jednocześnie należeć do zbioru niezależnego. trzy przypadki:
1. tylko czerwony należy- mamy \(\displaystyle{ d_{l-3}+d_n}\) takich zbiorów
2. tylko różowy należy - \(\displaystyle{ d_{n-1}+d_{l-3}}\)
3. żaden z nich nie należy do rozpatrywanego zbioru: \(\displaystyle{ d_{l-2}+d_n}\)
sumujemy, wykorzystujemy poprzednie spostrzeżenia i gotowe. wszystko jasne?