szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 6 mar 2015, o 15:14 
Użytkownik

Posty: 412
Lokalizacja: Bielsko-Biała
Hej, czy moglby mi ktos wytłumaczyc co to jest graf nieskonczony, ewentulanie podac literature gdzie tego szukac?

Z góry dzięki
Góra
Mężczyzna Offline
PostNapisane: 6 mar 2015, o 16:24 
Korepetytor
Avatar użytkownika

Posty: 3986
Lokalizacja: Praga, Dąbrowa Górnicza, Kraków
Graf nieskończony to graf, który ma nieskończoną liczbę wierzchołków.

http://www.math.uni-hamburg.de/home/die ... tions.html
Góra
Kobieta Offline
PostNapisane: 7 mar 2015, o 00:21 
Użytkownik

Posty: 412
Lokalizacja: Bielsko-Biała
I to jst formalna definicja?
Np. jakby miala teraz narysowac sciezke nieskonczona to bedzie to sciezka o nieskonczonej liczbie wierzcholkow, natomiast promiec nieskonczony bedzie mial nieskonczona liczbe wierzcholkow tylko z jednej strony? Mam podac definicje plus przyklady takiego grafu na referacie dlatego, pytam o cos formalnego.

Przy okazji, mam jeszcze problem z definicja grafu losowego. Wiesz moze cos na ten temat?
http://en.wikipedia.org/wiki/Rado_graph ... ry_numbers - znalazlam cos takiego i probuje sie wczytac, jednak jakby ktos mi to wytlumaczyl tak lopatologicznie to na pewno duzo skorzystam;)
Góra
Mężczyzna Offline
PostNapisane: 7 mar 2015, o 00:44 
Korepetytor
Avatar użytkownika

Posty: 3986
Lokalizacja: Praga, Dąbrowa Górnicza, Kraków
Nie rozumiem tego pędu za formalnością. Matematyka to nie jest tłumaczenie rzeczy prostych na rzeczy, które brzmią mądrzej. Graf nieskończony to graf, który jest nieskończony. Kropka.

Teoria grafów nieskończonych skupia się na nieskończonej teorii Ramseya dla grafów. Nieskończone twierdzenie Ramseya jest pięknym twierdzeniem o... grafach nieskończonych. Możesz pokazać wspaniały kontrprzykład Sierpińskiego o tym, że nie można tego twierdzenia rozszerzyć na grafy o \aleph_1 wierzchołkach, ale na (2^{\aleph_0})^+ już tak.

Nawet symbol w moim podpisie odnosi się do nieskończonej teorii grafów (twierdzenie Erdősa–Rado). Jeżeli znasz trochę teorii modeli możesz opowiedzieć o klasie Fraïsségo grafów skończonych, których granicą Fraïsségo jest graf Rado (graf losowy o którym wspominasz).
Góra
Kobieta Offline
PostNapisane: 7 mar 2015, o 01:12 
Użytkownik

Posty: 412
Lokalizacja: Bielsko-Biała
Okej, w takim razie nie komplikuje sobie zycie.
W te twierdzenia dopiero musze sie wczytac, bo bedzie to juz dodatkowy material, to sprawdz jeszcze prosze te jedna rzecz.

Cos takiego znalazlam:
"Ackermann (1937) and Rado (1964) constructed the Rado graph using the BIT predicate as follows. They identified the vertices of the graph with the natural numbers 0, 1, 2, ... An edge connects vertices x and y in the graph (with x < y) whenever the xth bit of the binary representation of y is nonzero. Thus, for instance, the neighbors of vertex 0 consist of all odd-numbered vertices, because the numbers whose 0th bit is nonzero are exactly the odd numbers. The neighbors of vertex 1 consist of vertex 0 (the only vertex whose bit in the binary representation of 1 is nonzero) and all vertices with numbers congruent to 2 or 3 modulo 4. "

I chyba cos zle przetlumaczylam, bo rozumiem ze dwa wierzcholki moge ze soba polaczyc, jezeli numer bitu pierwszego wierzcholka jest rozny od zera w reprezentacji bitowej drugiego wierzcholka?
Dlaczego zatem sasiedzi zera, to liczby nieparzyste, skoro np w reprezentacji dwojki, pozycja zerowa tez jest rozna od zera?
Góra
Mężczyzna Offline
PostNapisane: 7 mar 2015, o 10:11 
Gość Specjalny
Avatar użytkownika

Posty: 4974
Lokalizacja: Lozanna
zerowy bit 2 to 0, bity liczy się od prawej
Góra
Kobieta Offline
PostNapisane: 7 mar 2015, o 21:45 
Użytkownik

Posty: 412
Lokalizacja: Bielsko-Biała
Faktycznie, dziekuje. Mam jeszcze pytanie do sasiadow wierzcholka o numerze jeden, rozumiem ze beda to wszystkie wierzcholki z numerami przystajacymi do dwa lub trzy modulo cztery, ale dlaczego bedzie tam jeszcze wierzcholek zero, skoro w binarnej reprezentacji na pierwszej pozycji ma on rowniez zero.

-- 8 mar 2015, o 21:42 --

Mam jeszcze problem z zagadnieniem: jak okreslic automorfizmy dla grafu nieskonczonego.
Wiem ze automorfizm to izomorfizm grafu na samego siebie, jak natomiast wyglada sytuacja w przypadku grafow nieskonczonych?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 3 zadania: szachownica, graf, rekurencja  jraven  3
 Graf Petersena nie posiada Cyklu hamiltonowskiego?  snowjay  2
 Jaka macierz przyległości aby WKKW na spójny graf - zadanie 2  sweetdream  2
 Oznaczenia grafów - jak narysować graf np. K3?  anusiakk  1
 Graf 5 skladowych  lutzi0  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl