Matematyka dyskretna, zadanie nr 896

Autor	Zadanie / 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