Witam. Mam drobny problem, mianowicie stanąłem przed zadaniami niezwykle trudnymi (przynajmniej dla mnie), do których nie mam kompletnie koncepcji, jak je rozwiązać - nie wiem, jak i od czego je zacząć. Zastanawiam się, jakie zagadnienia/teorię/wzory/twierdzenia/cokolwiek powinienem przeanalizować, zanim podejdę do tych zadań ? Póki co, nie mam na nie pomysłu.
Oto zadanka z którymi mam problem:
1. "Wykazać, że wśród pięciu punktów wybranych w trójkącie równobocznym o boku 1,
istnieje przynajmniej jedna para punktów odległych od siebie o co najwyżej ½." - Z zadankiem tym radzę sobie w ten sposób, że rysuję równoboczny trójkąt o boku 1. Następnie od każdego wierzchołka prowadzę wysokość, prostopadłą do Podstawy tego trójkąta. No i z własności trójkątów równobocznych można wywnioskować, że punkt przecięcia tych wysokości znajduje się na drugiej wysokości, punkt zatem dzieli naszą wysokość na dwa odcinki o długościach \(\displaystyle{ \frac{1}{3}h}\) oraz \(\displaystyle{ \frac{2}{3}h.}\) Tak to powinno mniej więcej wyglądać ??
Kolejne zadanko jest następujące:
2. "Pokazać, że każdy wielościan zawiera przynajmniej dwie ściany o tej samej liczbie
krawędzi." - Tu już zupełnie nie mam pomysłu, jak to zrobić. Jak mam to pokazać, matematycznie za pomocą jakiś obliczeń i wzorów, czy jakoś to narysować ? Tylko jak ?
3. "Wykazać, że w grafie prostym istnieją przynajmniej dwa wierzchołki tego samego
stopnia." - Graf prosty to taki, który zawiera jedną i tylko jedną krawędź łączącą dwa różne wierzchołki (choć to zapewne wielu z Was to wie). No i właśnie jak w przypadku zadania numer dwa, nie mogę tego chyba narysować. Mam to bowiem wykazać w przypadku każdego grafu prostego (potwierdzone info), tylko właśnie w jaki sposób to zrobić ?
W wyniku rozwiązania tego zadania doszliśmy do tego zapisu:
\(\displaystyle{ 2m = \sum_{}^{v \in V} deg(v)}\)
Gdzie \(\displaystyle{ m}\) jest to ilość krawędzi.
No i właśnie nie potrafię rozgryźć, co ten zapis oznacza i jak do niego dojść. W jaki sposób, przy użyciu jakich twierdzeń, własności i wzorów można coś takiego uzyskać ?
4. "Pokazać, że w grafie jest parzysta liczba wierzchołków o stopniach nieparzystych." - To chyba podobne zadanko, do tych powyższych, czyż nie ? Jak zatem je rozwiązać ?
5. "Jeżeli:
\(\displaystyle{ \left[ \left( \forall v \in V \right) deg v \ge 2 \right]}\)
w G istnieje pewien cykl (prosty)."
Co oznacza powyższy zapis ? Bo w obecnej formie nawet nie wiem za bardzo, jak mam podejść do tego zadania.
6. "W grafie dwudzielnym każdy cykl ma parzystą długość." - Jak mam to pokazać, udowodnić ?
7. "Udowodnij, że w dwudzielnym grafie o n wierzchołkach, liczba krawędzi jest równa co
najwyżej"
\(\displaystyle{ \left\lfloor \frac{ n^{2} }{4} \right\rfloor}\)
8. "Wykazać, że z dokładnością do izomorfizmu, istnieją dokładnie cztery grafy z trzema
wierzchołkami i jedenaście z czterema wierzchołkami."
9. "Narysuj wszystkie nieizomorficzne sześciowierzchołkowe grafy 3-regularne." - Jakie to są, jak wykazać, które to są i jak je narysować ?
10. "Udowodnij, że graf prosty G = (V;E) jest spójny wtedy i tylko wtedy, gdy przynajmniej
dwa grafy Gv, będące wynikiem usunięcia z G wierzchołka v z przyległymi krawędziami,
są spójne (n(G) > 2)." - Jak to wyliczyć i jak się do tego zabrać ??
No właśnie, jaka teoria/twierdzenia/wzory/ciekawostki/sztuczki mogą pomóc w rozwiązywania takich zadań ?? Jaki jest algorytm ich rozwiązywania ? Nie pytam o rozwiązanie, tylko o sposób rozwiązywania takowych zadań.
Dlaczego chcę się nauczyć rozwiązywać tego typu zadania ? Ponieważ te umiejętności mogą być w przyszłości przydatne i pomocne w moich zainteresowaniach. Tylko po prostu nie mam pomysłu, jak zacząć...
Zagadnienia związane z rozwiązywaniem zadań z grafami ?
-
gardner
Zagadnienia związane z rozwiązywaniem zadań z grafami ?
Mógłbym odpisać na każde z zadań po kolei i jeśli chcesz uzyskać pomoc to załóż do każdego temat z osobna. Chętnie się z nimi pomęczę,serio. A tak wyrywkowo to 5,6,7 są na prawdę proste. Trzeba znać tylko podstawowe oznaczenia i własności. Przerabiałeś coś z matematyki dyskretnej? Chyba nie,jeżeli nie wiesz że w zadaniu piątym zapis oznacza,że każdy wierzchołek ma stopień co najmniej 2.Co do 6 i 7 to wystarczą podstawowe własności grafu dwudzielnego. Załóż tematy to pomożemy bo w jednym chyba trochę bez sensu się odnosić do każdego zadania zwłaszcza,że na pewno będziesz miał pytania i się zrobi straszny burdel.
Odpowiadając na Twoje pytania to metody nie ma-trzeba wiedzieć o czym mowa w zadaniu i próbować matematycznie to zapisać,tak,żeby sprawdzający nie miał wątpliwości że wiesz o co chodzi i nie mógł się do czegoś przyczepić (np. znaleźć luki w Twoim rozumowaniu) Dobra metoda w rozwiązywaniu tego typu zagadnień jest również dowodzenie nie wprost
Odpowiadając na Twoje pytania to metody nie ma-trzeba wiedzieć o czym mowa w zadaniu i próbować matematycznie to zapisać,tak,żeby sprawdzający nie miał wątpliwości że wiesz o co chodzi i nie mógł się do czegoś przyczepić (np. znaleźć luki w Twoim rozumowaniu) Dobra metoda w rozwiązywaniu tego typu zagadnień jest również dowodzenie nie wprost