szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 20 sty 2017, o 13:20 
Użytkownik

Posty: 106
Iloma ciągłymi pociągnięciami ołówka można narysować figurę tak, aby nie rysować żadnej linii dwukrotnie.

Np. dla takiej figury:
http://www.mini.pw.edu.pl/MiNIwyklady/g ... lad/gr.gif

Istnieje jakaś zależność, twierdzenia, które pozwala takie zadanie obliczyć? Robić na piechotę, to raczej nie ma sensu, bo tych odpowiedzi, chyba jest dużo. Nie wiem czy akurat na tej figurze się da, ale ogólnie obrazuje przykład o co chodzi.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 20 sty 2017, o 15:16 
Użytkownik

Posty: 1074
Lokalizacja: Lublin/Warszawa
To nie figura, tylko graf!
Graf rysowany jednym pociągnięciem ołówka to ścieżka. Ty chcesz rozłożyć graf na minimalną liczbę ścieżek krawędziowo rozłącznych (bo nie chcemy przechodzić dwa razy po jednej krawędzi). Trzeba stwierdzić ile ich jest - to dość znane zadanie.

Ma ono związek z cyklami/ścieżkami Eulera - jeżeli żaden wierzchołek lub dokładnie dwa wierzchołki (nie może być tylko jeden, bo suma stopni byłaby nieparzysta) mają stopień nieparzysty to w grafie istnieje ścieżka Eulera (przechodząca przez wszystkie krawędzie grafu i przez każdą jeden raz) - można go narysować jednym pociągnięciem ołówka.

Pytanie co zrobić, gdy ma więcej wierzchołków nieparzystego stopnia:
Zauważ, że każda ścieżka ma w środku wierzchołki stopnia 2, a na końcach wierzchołki stopnia 1. Załóżmy, że rozłożyliśmy graf na minimalną liczbę ścieżek. Na pewno w każdym wierzchołku stopnia nieparzystego w grafie musiała mieć początek/koniec jakaś ze ścieżek (inaczej miałby stopień parzysty). Tak więc minimalna liczba ścieżek z których mógł on powstać jest równa:
x - liczbie wierzchołków nieparzystego stopnia (w danej spójnej składowej) podzielonej przez dwa.

Powyżej pokazaliśmy oszacowanie dolne na liczbę ścieżek. Teraz pokażemy, że rzeczywiście tyle ścieżek wystarczy poprzez podanie algorytmu podziału grafu na taką liczbę ścieżek:
Wiadomo, że w grafie liczba wierzchołków nieparzystego stopnia jest parzysta (bo suma stopni wszystkich wierzchołków grafu jest parzysta). Dodajmy do naszego grafu specjalne krawędzie, każda z nich niech łączy dwa inne wierzchołki nieparzystego stopnia - w ten sposób dodaliśmy do grafu x krawędzi. Nasz nowy graf ma wszystkie stopnie parzyste, więc ma cykl Eulera - znajdujemy ten cykl. Bierzemy ten cykl i usuwamy z niego wszystkie dodane krawędzie specjalne - nasz cykl rozpadnie się na dokładnie x rozłącznych krawędziowo ścieżek, bo każde dwie krawędzie specjalne na tym cyklu musiały być przedzielone przynajmniej jedną krawędzią z początkowego grafu (bo w każdym wierzchołku ma koniec maksymalnie jedna krawędź specjalna).

Oczywiście powyższe rozumowanie należy powtórzyć dla każdej spójnej składowej grafu osobno.
Odpowiedź to x dla spójnych grafów zawierających jakieś wierzchołki stopnia nieparzystego i 1 dla spójnej mającej cykl Eulera.

PS. Wygląda na to, że dla grafu który podałeś (a swoją drogą jest to jeden z grafów Mycielskiego) potrzeba przynajmniej trzech krawędziowo rozłącznych ścieżek (bo ma sześć wierzchołków stopnia nieparzystego).
Góra
Mężczyzna Offline
PostNapisane: 21 sty 2017, o 01:15 
Użytkownik

Posty: 106
Zgadza się.

Znalazłem jakieś TW w jednej z książek, które mówi, że dla grafu spójnego o k wierzchołkach nieparzystych stopni liczba tych ścieżek wynosi \frac{k}{2}, czyli dla tego przykładu \frac{6}{2}=3
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 kreska rysowana ołówkiem  Niezapominajka99  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl