logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Matematyka dyskretna, zadanie nr 896

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

megustaaa
postów: 2
2013-01-19 19:21:45

Ile różnych podgrafów posiada graf będący cyklem o 4 wierzchołkach?



tumor
postów: 8070
2013-01-19 20:21:37

Sam jest swoim podgrafem.

Na 4 sposoby możemy usunąć jedną krawędź, wierzchołków wtedy ruszyć nie możemy.

Na 2 sposoby możemy usunąć parę przeciwległych krawędzi, wierzchołków wtedy ruszyć nie możemy

Na 4 sposoby możemy usunąć dwie sąsiednie krawędzie, przy tym albo eliminujemy wierzchołek, który był między nimi, albo nie (czyli 8 możliwości).

Na 4 sposoby możemy usunąć 3 krawędzie. Zostaną 2 wierzchołki niepodpięte krawędziami. Możemy usunąć każdy lub nie, co da 4 warianty (razem 16)

No i na 1 sposób usuwamy wszystkie krawędzie, zostają 4 wierzchołki, czyli $2^4-1=15$ wariantów (bo liczba wierzchołków nie jest 0).

1+4+2+8+16+15=46

Nie pamiętam twierdzeń, które by pozwoliły liczyć to w ogólnym przypadku :P

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj