Matematyka.pl

Digraf ma \(\displaystyle{ 2m}\) krawędzi. Udowodnić, że można usunąć jakieś \(\displaystyle{ m}\) z nich tak, aby nie było cyklu.

Zakładam, że graf ten posiada krawędzie, krawędzie są strzałkami oznaczającymi kierunek, , w krawędzi nie ma podwójnych strzałek,
Nie ma też pętelek...

Czyli macierz , która reprezentuje ten graf ma postać (macierz sąsiedztwa):

\(\displaystyle{ a_{i,j}=0,1}\)

jeżeli

\(\displaystyle{ a_{i,j}=1 }\)

to

\(\displaystyle{ a_{j,i}=0, a_{i,i}=0}\)

Jeżeli teraz mamy parzystą ilość jedynek czyli parzystą liczbę krawędzi przy powyższych warunkach...

"Najgorszy" przypadek to taki, że powyżej i poniżej głównej przekątnej będą jedynki w tej samej ilości po:\(\displaystyle{ m }\)

Jeżeli dla ustalenia uwagi zabierzemy wszystkie jedynki z dołu głównej przekątnej to tak jakbyśmy usunęli m krawędzi, macierz zostanie górnotrójkątna z zerami na głównej przekątnej. Macierz \(\displaystyle{ A}\)

Wyznacznik macierzy:

\(\displaystyle{ I-A}\) będzie różny od zera (ponieważ liczymy tak jak ślad macierzy) co znaczy, że graf nie zawiera cykli, cnd...

Innymi słowy: wystarczy liniowo uporządkować graf i usunąć wszystkie krawędzie idące "w górę" lub wszystkie idące "w dół", w zależności od tego których jest mniej.

arek1357 pisze: ↑4 wrz 2022, o 22:32 jeżeli

\(\displaystyle{ a_{i,j}=1 }\)

to

\(\displaystyle{ a_{j,i}=0, a_{i,i}=0}\)

Nie wiem, skąd wnioskujesz, że \(a_{j,i}=0\), ale też nie widzę, żeby brak tego założenia w czymś przeszkadzał.

arek1357 pisze: ↑4 wrz 2022, o 22:32 Wyznacznik macierzy:

\(\displaystyle{ I-A}\) będzie różny od zera (ponieważ liczymy tak jak ślad macierzy) co znaczy, że graf nie zawiera cykli, cnd...

Czy \(\det(I-A)=0\) to warunek konieczny istnienia cyklu?

Mogłeś tu stwierdzić, że dla każdego \(k\in\mathbb{N}_+\) macierz \(A^k\) ma same zera na przekątnej, więc graf nie ma cykli.

Założyłem, że graf ten nie ma pętelek, możliwe, że jakby miał pętelki to też teza by spełniona była.
A tak czy siak zrobiłem jak było mi wygodniej, pokaż teraz swoją propozycję tak od początku...

Napisałem że jeżeli:

\(\displaystyle{ a_{i,j}=1}\)

to musi być

\(\displaystyle{ a_{j,i}=0}\)


I na odwrót

Inaczej krawędź jakaś mogłaby mieć strzałki w obie strony a to raczej nie byłoby wskazane...

Tak samo wykluczyłem pętelki...

arek1357 pisze: ↑5 wrz 2022, o 09:29 pokaż teraz swoją propozycję tak od początku...

Nie mam własnej propozycji. Ogólnie zgadzam się z Twoim rozwiązaniem po uwzględnieniu moich uwag. I zgadzam się z tym, jak to rozwiązanie podsumował Dasio11.

arek1357 pisze: ↑5 wrz 2022, o 09:33 Inaczej krawędź jakaś mogłaby mieć strzałki w obie strony a to raczej nie byłoby wskazane...

Dlaczego byłoby niewskazane? Przecież to w żaden sposób nie wpływa na Twój dalszy tok rozumowania. Wydaje mi się naturalną sprawą, że w grafie skierowanym mogą być krawędzie w obie strony pomiędzy tymi samymi wierzchołkami.

Więc rób to zadanie dla grafu w którym są pętelki i strzałki, które mogą lecieć w dwóch kierunkach...

Z pętelkami raczej nie wyjdzie. A czy w tym zadaniu krawędzie w obie strony są zabronione, tego nie wiem. Przypuszczam, że nie.

Oczywiście, że z pętelkami nie wyjdzie bo musiałbyś traktować je jak krawędzie a strzałki w obie strony jakby były to można polec na macierzach...
Dlatego od razu porobiłem odpowiednie założenia dla tego zadania...