Zadania są mało szczegółowe, ale takie dostałem od profesora, tam gdzie brakuje jakiegoś grafu czy czegokolwiek innego to po prostu trzeba sobie to samemu wymyśleć
1. Dla jakich m,n, graf Knm(dwudzielny) posiada ścieżkę, cykl eulera,cykl hamiltona
2. Dla grafu siatkowego Gmn(grid graph) wyznaczyć cykl hamiltona
3. Zbadać twierdznie Chvatala na grafie z cyklem hamiltona
4. Wyznaczyć ilośc krawędzi do usuniecia lub dodania aby graf byl plaski ,planarny
5. Skojarzenia w grafie dwudzielnym
6. znak permutacji na podstawie liczby inwersji <n-1,n,….,5,6,3,4,1,2>
bardzo pilne...
zadania na zaliczenie, ważne
-
- Użytkownik
- Posty: 2
- Rejestracja: 21 cze 2017, o 15:47
- Płeć: Mężczyzna
- Lokalizacja: Polska
-
- Użytkownik
- Posty: 2
- Rejestracja: 21 cze 2017, o 15:47
- Płeć: Mężczyzna
- Lokalizacja: Polska
zadania na zaliczenie, ważne
1 zadanie robiłem metodą prób i błedów i doszedłem tylko do pewnych wniosków:
-graf K(n,m) posiad ścieżkę Eulera dla n=2 i m nieparzystych
-cykl Eulera dla parzystych n i m
- cykl hamilitona dla n=m
2 zdanie doszedlem do wniosku po kilku wykonanych grafach że grid graf posiada cykl hamiltoona gdy n lub m należy do nieparzystych
3. nie wiem
4. próbowałem na podstawie stowrzonego przez siebie grafu jestem w stanie dodać lub usunąć kilka krawędzi w grafie by byl planarny ale nie wiem czy da się to jakoś wyznaczyć matematycznie
5. moje spostrzezenia są takie że skojarzeń w grafie dwudzielnym K(n,m) jest: n jesli n<m lub m jesli m<n
6. podstawiając za n liczby za każdym razem wychodziła mi parzysta liczba inwersji. znak permutacji (-1)^liczby_inwersji=1
-graf K(n,m) posiad ścieżkę Eulera dla n=2 i m nieparzystych
-cykl Eulera dla parzystych n i m
- cykl hamilitona dla n=m
2 zdanie doszedlem do wniosku po kilku wykonanych grafach że grid graf posiada cykl hamiltoona gdy n lub m należy do nieparzystych
3. nie wiem
4. próbowałem na podstawie stowrzonego przez siebie grafu jestem w stanie dodać lub usunąć kilka krawędzi w grafie by byl planarny ale nie wiem czy da się to jakoś wyznaczyć matematycznie
5. moje spostrzezenia są takie że skojarzeń w grafie dwudzielnym K(n,m) jest: n jesli n<m lub m jesli m<n
6. podstawiając za n liczby za każdym razem wychodziła mi parzysta liczba inwersji. znak permutacji (-1)^liczby_inwersji=1