szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 17 cze 2015, o 20:59 
Użytkownik

Posty: 54
Lokalizacja: Kraków
Witam,

1. Czy prawdą jest, że jak mamy graf skierowany z tylko jednym wierzchołkiem i w tym wierzchołku jest pętla, to wtedy stopień tego wierzchołka jest 2? Jeśli tak, to dlaczego, skoro idziemy tylko w jedną stronę?

2. Czy prawdą jest, że szkielet grafu to ten sam graf, tylko z usuniętymi strzałkami z krawędzi, przy czym same krawędzie pozostają tak jak były?

3. Czy prawdą jest, że graf jest drogą Eulera, jeżeli jest spójny i ma dokładnie 2 wierzchołki stopnia nieparzystego?

4. Czy prawdą jest, że graf jest cyklem Eulera, jeżeli jest spójny oraz ma wszystkie wierzchołki stopnia parzystego?

Pozdrawiam!
Góra
Mężczyzna Offline
PostNapisane: 17 cze 2015, o 22:08 
Gość Specjalny

Posty: 5793
Lokalizacja: Toruń
1. Nie. Stopień wejściowy wynosi 1, stopień wyjściowy także 1.

2. Nie. Szkielet grafu to inaczej najkrótsze drzewo rozpinające.

3. Tak.

4. Tak.
Góra
Mężczyzna Offline
PostNapisane: 18 cze 2015, o 08:15 
Użytkownik

Posty: 54
Lokalizacja: Kraków
1. Mi właśnie chodzi o stopień ogólny, bez podziału na wejściowe czy wyjściowe, według Wikipedii:
https://pl.wikipedia.org/wiki/Stopie%C5 ... ho%C5%82ka

Cytuj:
Stopień wierzchołka – liczba krawędzi grafu sąsiadujących z wierzchołkiem. Jest on równy sumie liczb wszystkich łuków wchodzących, wychodzących, krawędzi i pętli; każdą pętlę liczy się jednak jak dwie krawędzie. W grafach skierowanych można też wyróżnić stopień wchodzący i stopień wychodzący. Są to odpowiednio liczby łuków wchodzących do i wychodzących z wierzchołka.


Z podkreślonego fragmentu wynika, że stopień tego wierzchołka to jest 2. Dobrze myślę? Chodzi mi o stopień wierzchołka bez podziału na wchodzące i wychodzące.

2. Czy jesteś w stanie podać jakiś przykład? W Google ciężko znaleźć jednoznaczną definicję szkieletu grafu.

-- 18 cze 2015, o 07:32 --

Co do punktu 2:

http://wazniak.mimuw.edu.pl/index.php?t ... _12:_Grafy

Tutaj na prawo jest przykład o nazwie "(a.) Digraf oraz (b.) jego graf szkieletowy", na którym dość wyraźnie jednak widać, że szkielet grafu powstał poprzez usunięcie strzałek z grafu podstawowego?

-- 18 cze 2015, o 07:40 --

Tutaj również:

http://www.google.pl/url?sa=t&rct=j&q=& ... 2g&cad=rja

Cytuj:
Graf Szkieletowy – diGraf po zignorowaniu grotów krawędzi
Góra
Kobieta Offline
PostNapisane: 13 wrz 2015, o 05:49 
Użytkownik

Posty: 1
Lokalizacja: Polska
Wątek trochę stary, ale dla potomności coś naskrobię.
xxxtaruoxxx napisał(a):
2. Czy jesteś w stanie podać jakiś przykład? W Google ciężko znaleźć jednoznaczną definicję szkieletu grafu.
Niestety nie jest to wina Google, lecz samej teorii grafów i sieci, która charakteryzuje się właśnie tym, że nie ma ustandaryzowanych definicji :/ Zdaje się, że matematyczne koncepcje w niej zawarte są uniwersalne, ale już tłumaczenie ich na język "ludzki" potrafi się znacząco różnić w zależności od tego, z jakiego autora korzystasz.
Jeśli uczysz się pod egzamin, bardzo ważne jest, by opierać się na materiałach zaleconych przez prowadzącego właśnie po to, by uniknąć niejednoznaczności. Wystarczy, że jedno oznaczenie/nazwa będzie inne od tego, którego uczyłeś się Ty i już na egzaminie możesz mieć niezłą wodę z mózgu :)

W wykładach mojego psora (opartych bodajże na Korzanie) jest taka definicja szkieletu grafu:
"Szkielet grafu G - taki graf zwykły Gs = <W, Us>, że:
{x,y} \in Us \Leftrightarrow x \neq y oraz x i y są przyległe w G"
i nic więcej, więc też mam z nią trochę problemu, bo wg mnie nie jest jednoznaczna. Biorąc pod uwagę, że graf zwykły nie może zawierać pętli, łuków ani n-krotnych połączeń między wierzchołkami, to wiadomo, że pętle, łuki (krawędzie ze strzałkami) i np. podwojone krawędzie trzeba wywalić, ale nie jest przecież sprecyzowane, czy można wywalić wszystkie krawędzie łączące dwa wierzchołki, czy też musi pozostać przynajmniej jedna krawędź? Sama definicja grafu zwykłego z Korzana mówi o CO NAJWYŻEJ jednej krawędzi między wierzchołkami, czyli może być 1 lub 0 krawędzi.
Patrząc dalej w definicji widzimy tylko, że Us \subseteq U, w Us nie może być pętli oraz jeśli w pierwotnym grafie nie było połączenia między wierzchołkami, to nie można tego połączenia dorysować w szkielecie grafu (co jest dość oczywiste), ale znowu nie jest sprecyzowane, czy można pominąć jakąś krawędź łączącą 2 wierzchołki w szkielecie grafu.

Z tego co pamiętam z ćwiczeń, nie pomijaliśmy żadnej krawędzi z pierwotnego grafu (poza oczywiście zwielokrotnionymi połączeniami) ale jestem bardzo ciekawa, czy można to zrobić i czy nadal będzie to szkielet grafu, czy może już część szkieletu grafu.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Dziedzina relacji??  stumi  2
 dane na podstawie wyniku & liczby z losowanych cyfr  pijtagolas  1
 Pare problemów kombinatorycznych  Stork  3
 Macierz relacji - zadanie 2  niunian  1
 Parę zadań - zadanie 8  Alecx  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl