Szukaj

narzędzia

Dyskusja:Graf (matematyka)

Spis treści

[edytuj] Do weryfikacji

Skąd informacja: Za twórcę pojęcia grafu uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich.? Prosiłabym o podanie źródła? 4^@ 15:33, 12 maja 2006 (CEST)

Zdaje się, że Rnm dodał [1]. Zapytam, bo sam nie kojarzę takiej informacji. --Nux ^>dyskusja< 16:07, 19 maja 2006 (CEST)

Z en Wiki:

1736: Euler solved, or rather proved insoluble, a problem known as the seven bridges of Königsberg, publishing a paper Solutio problematis ad geometriam situs pertinentis which was the earliest application of graph theory or topology.

Superborsuk ^Ω 02:34, 20 maja 2006 (CEST)

Hm... Zgdonie z tym nie stworzył pojęcia grafu, tylko raczej stworzył pierwszą naukową publikację dotyczącą teorii grafów. --Nux ^>dyskusja< 13:37, 20 maja 2006 (CEST)

Czepiasz się - Right i Wross piszą "pierwszym naukowcem zajmującym się teorią grafów był Euler." i tak samo piszą, że grafem jest siatka jak i automat skończony jak i schemat blokowy - z nimi też sie bedziesz kłócił? Rnm 09:13, 26 maja 2006 (CEST)

To nie jest czepianie się. Moje pytanie było precyzyjne i dotyczyło wprowadzenia samego pojęcia grafu, a nie zajmowania się grafami. Badaniem funkcji też zajmowano się zanim powstała precyzyjna definicja. Jeśli nie ma źródeł (ja ich nie znam), to sporny fragment należy przeredagować, by nie było podobnych "kontrowersji". Nux słusznie zauważył, że fragment zacytowany przez Superborsuka tego nie rozstrzyga. 4^@ 20:13, 14 cze 2006 (CEST)

"...zajmującym się teorią grafów...", a nie "...twórcą grafów..." i tu się zgadzamy :). Może tam piszą raczej, iż siatkę można uprościć do grafu? Bo i siatka i automat (skończy, czy nieskończony) są bardziej skomplikowane niż sam graf, które jako taki możnaby zgrubsza reprezentować. Np. siatkę topologiczną terenu można zareprezentować jako graf z wagami, żeby rozwiązać problem najkrótszej drogi. Wystarczy wgryźć się w formalną definicję grafu, żeby zobaczyć gdzie jest różnica. No chyba, że ktoś gdzieś tam widzi np. podział wierzchołków na rodzaje: "wykonaj", "wybierz" itp (występujące w schematach blokowych). Czy występuje tam jakieś zdanie podobne do tego: "do każdego wierchołka przyporządkowane są dwie liczby, które stanowią o jego pozycji"? W en:Graph_(mathematics) przynajmniej od razu wiadomo czym z grubsza jest graf, a tutaj początek jest jak dla mnie bardzo mylący i tego się czepiam. --Nux ^{zostaw notkę} 11:13, 26 maja 2006 (CEST)

PS: A przy okazji - skąd pochodzi pojęcie grafy geometryczne? Może to jakieś diagramy chodzi?

graf to zbiór punktów/kwadratów/łososi połączonych krawędziami/linkami/czarnymi dziurami - to mówi definiicja grafu - dwa 'zbiory i funckja z par pierwszego w drugi. I tak oto zgodnie z tą defincją wymieniane przezemnie rzeczy są "pelnoprawnymi" grafami. To prochę tak jakdybyś się czepiał definicji pojazdu - pojazd to coś jeżdzące, ale nie samochód bo on ma karoserię, 4ry koła i inne rzeczy których nie ma pojazd. Tylko że to o polimorfizm chodzi, niektóre rzeczy są szczególnym rodzajem rzeczy innych, co nie sprawia, że nie są tymi innymi :)

określenie grafy geometryczny pochodzi z zarysu teorii grafów - nie chodzi o diagramy, ale o to czy np. dany graf można "upchać" w danej przestrzeni, albo np. o czy da się go tak ustawić, by wszystkie krawędzie miały tą samą długość w konkretnym przedstawieniu grafu. Wytlusciłem to, bo odnoszę wrażenie, że nie do końca rozumiesz różnicę między pojęciem grafu a jego konkretnymi rysunkami Rnm 12:23, 26 maja 2006 (CEST)

O ile wiem mówi się raczej o geometrycznej teorii grafów, czy mógłbyś podać jakieś źródło, gdzie występuje pojęcie graf geometryczny? Kuszi 19:02, 14 cze 2006 (CEST).

Definicja z którą się częściej spotykam traktuje graf jako dwa zbiory: zbiór wierzchołków i zbiór par wierzchołków. Nie rozumiem wypowiedzi wikipedysty Rnm - można mówić o grafie automatu, nie znaczy to jednak, że oba obiekty są tożsame. Kuszi 18:51, 14 cze 2006 (CEST).

[edytuj] Formalna definicja

Czy aktualna formalna definicja

 funkcją ze zbioru krawędzi w dwuelementowy podzbiór zbioru wierzchołków -  gdzie

jest poprawna? Bo ten wzór mówi, że wartościami funkcji są elemty zbioru {u,v}. Wydaje mi się, że powinno być coś takiego:

 funkcją ze zbioru krawędzi w zbiór dwuelementowych podzbiorów zbioru wierzchołków -

royas 08:25, 6 sie 2006 (CEST)

Słusznie, jest źle. Tak jak napisałeś jest lepiej. Jeszcze lepiej, bo prościej, byłoby zdefiniować graf jako dwójkę, tak jak np. w książce "Wprowadzenie do teorii grafów" Wilsona. Kuszi 10:10, 12 sie 2006 (CEST).

[edytuj] Graf mieszany

Fragment

Jeżeli graf skierowany zawiera dwie krawędzie skierowane \! (v,u) i \! (u,v), to nazywany jest grafem mieszanym.

nie zgadza się z definicją w graf mieszany. Która jest prawidłowa? royas 08:25, 6 sie 2006 (CEST)

W zasadzie obie można uznać za poprawne. Graf mieszany zawiera krawędzie nieskierowane i skierowane (łuki). Przy czym krawędź nieskierowaną można modelować dwoma łukami łączącymi te same wierzchołki. Pozdrawiam Kuszi 10:21, 7 sie 2006 (CEST).

Można modelować to nie znaczy, że są to te same grafy. Właściwie to jest głębsza różnica między tymi dwoma definicjami. Pierwsza to graf, który zawiera jakieś tam krawiędzie, durga - może zawierać, ale nie musi, bo E lub A może być puste. royas 20:45, 20 sie 2006 (CEST)

[edytuj] Osobne definicje

> Ścieżka w grafie to ciąg wierzchołków połączonych krawędziami.

Mam taką wątpliwość, czy warto pisać artykuł "ścieżka" - skoro tak naprawdę jest to krótko i dobitnie opisane tutaj (w grafie)?

A może tu skasować, napisać osobny artykuł o ścieżce i utworzyć link do niego?

To samo dotyczy: cyklu, grafu planarnego, itd.

Grzegon "McCartney" Olędzki 23:25, 8 kwi 2003 (CEST)~

[edytuj] Rozwinięcie artykułu

Początek uczyniłem, bardziej literackim, żeby czytelnika nie odstraszać nudną listą. Sądzę, że wszystkie zagadnienia dotyczące drzew (wyrażenia, binarne itp) należy pominąć. Mamy oddzielny artykuł o drzewach i tam najlepiej to opisać, a tutaj najlepiej skupić się na zagadnieniach typowych dla grafów. W tym momencie mamy 12 stron A4 i spis treści na cały ekran. Więcej treść raczej rozsadzi tekst od środka, więc należy się zastanowić nad niewielkim rozbiciem. Na początek sądzę, że jednak lepiej byłoby w artykule o grafie skupić się na matematycznej definicji grafu skierowanego - to przypadek najbardziej ogólny. Szczególne przypadki grafu nieskierowanego i mieszanego najlepiej opisać w ich artykułach. Superborsuk ^Ω 02:23, 29 kwi 2006 (CEST)

[edytuj] Zsynchronizowanie macierzy

Jakby ktoś mógł, to dobrze by było "zsynchronizować" macierze incydencji i krawędzi i resztę, tak żeby wszystko przedstawiało ten sam graf. Nux ^{zostaw notkę} 19:33, 4 cze 2006 (CEST)

ależ właśnie przedstawia :) RnM - ^D#&%kutuj

[edytuj] Potrzeba dopracowania

Trzy miesiące temu Nux bez podawania konkretnych zarzutów wrzucił infoboc do dopracowania. Czy waszym zdaniem jeszcze coś trzeba tu dopracować? Superborsuk ^Ω 02:12, 20 sie 2006 (CEST)

Lokalnie dużo dobrej informacji, ale spójrzmy na artykuł całościowo. IMHO wstęp-definicja nie najlepsze: po ogólnym uproszczonym opisie powinna zaraz pójść definicja formalna - tak jak stoi to drugi akapit posługuje się pojęciami niezdefiniowanymi. Mimo że mamy tu linki to w porządnym pisaniu tego się bardzo unika. Z resztą ten akapit raczej niewiele już wnosi, bo wiele załatwiłaby w tym miejscu dobra definicja. Kolejne akapity opisują coś, co raczej powinno się zebrać w osobną sekcję "Zastosowania" i przenieść poza wstęp gdzie chyba jest miejsce na podstawowe definicje i objaśnienia. Jeśli nie będzie obiekcji to spróbuję to podrzeźbić - właściwie chodzi raczej o pewne przetasowanie niż zmianę treści. --Beaumont 19:55, 20 sie 2006 (CEST)

J.w. tzn popieram zdanie Beaumonta. Poza tym art robi się trochę przydługi. Można by ewentualnie przenieść zastosowania do osobnego artu, albo do teorii grafów. Cała sekcja o przechowywaniu w pamięci nie musi wszystkich interesować, mogłaby pójśc do nowego artu, powiedzmy Algorytmy grafowe, zwłaszcza że jest już taka kategoria. Z drugiej strony brakuje choćby wzmianki o uogólnieniach, takich jak hipergrafy. Kuszi 20:53, 20 sie 2006 (CEST).

Jeszcze drobna uwaga. Pojęcie graf geometryczny nie wydaje się dobrze ugruntowane, zwłaszcza w języku polskim. Byłbym wdzięczny za jakąś notkę, gdzie zostało ono użyte. Kuszi 20:53, 20 sie 2006 (CEST).

Dzięki za post. Dla porządku:

Grafy geometryczne po polsku jakoś nieznane(gugel milczy), ale po angielsku całkiem całkiem. Najwidoczniej to nowy prąd który - jak wszystko teraz - pisze się po angielsku... Tutaj podaną definicję można by doszlifować, ale nie jest taka zła, a na pewno lepsza niż stub w enwiki. Ja bym to włączył do sekcji "Klasy grafów".
Tak samo uwaga o "Grafach nieskończonych" nie zasługuje na osobną sekcję, to przypisek do definicji, tyle że od niej oddzielony
no i teraz mamy trzy definicje:najpierw na początku, potem sekcja "Definicja", potem coś-tam i dalej "Definicja formalna". Nux miał rację. Poprawimy ;) pozdr. --Beaumont 22:52, 20 sie 2006 (CEST)
Aha, przyjrzałem się formalnej definicji i mam poważną wątpliwość co do pętli w przypadku grafu nieskierowanego: tam jest źle bo {v,v}={v} więc zbiór jednoelementowy. W linkowanej książce on-line pętle definiuje się tylko dla grafów skierowanych i tam to ma sens. Trzeba to wszystko poprawić - może zmieniając def. grafu skierowanego jak sugerowałeś, na dwójkę (V,E). No, jest nad czym pracować! jeszcze trochę się przyjrzę i idę robić. pozdr. --Beaumont 23:32, 20 sie 2006 (CEST)

Zdefiniowanie jako dwóki (V,E) raczej nie poprawi sytuacji z pętlą, bo i tak wtedy E musiałoby być podzbiorem zbioru jedno i dwuelemntowych podzbiorów V; co równie dobrze można włożyć do definicji z trójką. No właśnie chyba lepiej zamiast {V,E,g} dać (V,E,g} lub <V,E,g>. royas 00:21, 21 sie 2006 (CEST)

To bardzo dobry pomysł. Przeniósłbym jeszcze gęstość grafu z definicji do pojęć podstawowych. royas 00:21, 21 sie 2006 (CEST)

wyjaśniam więc: proponowałem - tak jak Kuszi - "dwójkę", bo tak prościej a nie dlatego że to rozwiązuje problem pętli. Z grubsza graf to dwójka (V,E) gdzie V to wierzchołki a E to krawędzie czyli rodzina dwuelementowych podzbiorów V, i już. Zapisu (V,E,g} nie rozumiem , sorry, a zapis <V,E,g> czyli trójka uporządkowana nic nie zmienia w porówaniu a aktualną wersją, sorry, nie o to chodziło.

Błąd, miało być (V,E,g), ale nieważne teraz. Definicja z trójką jest o tyle lepsza, że obejmuje również multigrafy, ale się nie upieram, moża ją przenieść do multigrafu. royas 11:33, 21 sie 2006 (CEST)

Chodzi o to żeby raczej w ogóle nie definiować pętli dla grafów nieskierowanych. Na obrazku jest ona łatwa do pomyślenia a formalna definicja nie pasuje. Jak chesz mieć pętlę w grafie (pozornie) nieskierowanym to musisz zdefiniować graf skierowany symetryczny i tam to istnieje. A najlepiej w ogóle nie definiować formalnie grafu nieskierowanego, tylko skierowany bo tak ogólniej - i problem znika: V to zbiór wierzchołków a E, krawędzie, to pary uporządkowane. Powtórzę - w takim ujęciu graf nieskierowany jest równoważny zywkłemu grafowi symetrycznemu. Krótko: gdyby ktoś miał porządną książkę matematyczną (do definicji formalnej) to by coś zapodał? - Kuszi, masz tego Wilsona to wal śmiało, jak nie to mocno proponuję to co tu powyżej. Pozdr --Beaumont 10:23, 21 sie 2006 (CEST).

Faktycznie, można nie definiować, będzie poprostu definicja grafu bez pętli. Trudno określić który graf jest najbardziej podstawowy, więc można wybrać to co najprostrze, czyli nieskierowany, nie multigraf, bez pętli, bez wag. royas 11:33, 21 sie 2006 (CEST)

To zasadniczo racja, ale zauważ że wszystkie reprezentacje w tym artykule (macierz sąsiedztwa,lista sąsiedztwa i macierz incydencji) faktycznie reprezentują graf *skierowany*, no więc dla spójności artykułu trzeba by ten skierowany zdefiniować. Czyli po tym namyśle mogłyby być dwie definicje skierowanego i nieskierowanego, tyle że już bez pętli --Beaumont 13:02, 21 sie 2006 (CEST)

Oczywiście. Chodziło mi o prostszą definicję grafu nieskierowanego (czy z pętlą, czy bez). Skierowany jak najbardziej zostawić. Fajnie i dosyć jasno jest to zrobione na enwiki. Fragment przetłumaczyłem na Wikipedysta:Royas/graf royas 13:43, 21 sie 2006 (CEST)

To jest ok. Zwróć tylko uwagę na pisownię "uporządkowany". Poza tym wydaje mi się że w języku polskim digraf nie istnieje, mówi się po prostu graf skierowany (rzut oka w google pokazuje że digraf to firmy nie grafy, ale może niedokładnie patrzyłem - jak masz jakiś ważny przykład używania to zostaw). No i chyba można by już zmieniać definicję tak jak proponujesz (potem ewent. dalsze porządki). --Beaumont 13:55, 21 sie 2006 (CEST).

A w czym problem z tą petlą? {v,v} - to zbiór dwuelementowy i jest różny od {v}. --Maciej "Nux" Jaros **zostaw notkę** 05:33, 21 sie 2006 (CEST).

No nie wiem. Zobacz Inkluzja (matematyka). Równość zbioru to nie "taki sam wygląd" tylko formalnie dwie inkluzje, a wygląda mi - o dziwo! - że zgodnie z formalną definicją mamy {v,v} $\subset$ {v}. Jeśli zamiast zbioru weźmiemy parę uporządkowaną, problem zniknie bo para (v,v) ma sens. Notabene zdaje się jak reprezentujemy graf w komputerze to z logicznego punktu widzenia zawsze mamy do czynienia z parami uporządkowanymi (albo ciągami) czyli robimy de facto graf skierowany i nie ma problemu. Tu zaś mamy pewien problem formalny - może mało ważny w praktyce - ale to w końcu encyklopedia i jakoś trzeba to zwalczyć. Pozdr. --Beaumont 10:23, 21 sie 2006 (CEST)
A i B są równe gdy dla każdego x: x należy do A wtedy i tylko wtedy gdy x należy do B. Więc {v,v} = {v} i oba są zbiorami jednoelemtowymi. royas 11:33, 21 sie 2006 (CEST)

No właśnie, dzięki że tak to prosto ująłeś. No i z tego widać że w naszej definicji formalnej mamy pewien błąd. --Beaumont 13:02, 21 sie 2006 (CEST)

Coś wam obu się pokręciło - podstawmy sobie pod v banknot stu złotowy. Czy jeśli mam zbiór dwóch takich banknotów, to jest on zawarty w zbiorze składającym się z jednego banknotu ;)? Zamiast formalnych rozważań czasem wystraczy trochę logiki. Matematyka naprawdę stara się odnosić czasem do rzeczywistości ;). Natomiast uporządkowanie takiego zbioru już specjalnie nie ma sensu, chyba że banknoty traktujemy jako rozróżnialne, ale wtedy to jest (v1,v2). --Maciej "Nux" Jaros **zostaw notkę** 16:15, 21 sie 2006 (CEST)

Hm, mocne wejście. My tu jednak o definicji formalnej mówimy, więc potrzeba dużej ścisłości, logika w znaczeniu "zdrowy rozsądek" może nie wystarczać... Przemyślisz?. --Beaumont 21:53, 21 sie 2006 (CEST)

PS: Tu przy okazji wniosek, że pętla jednokierunkowa nie ma właściwie sensu.
czy ktoś mówił o pętli jednokierunkowej? Ja tylko o pętli w grafie skierowanym, a to na pewno istnieje i ma prosty sens: ot para (v,v) w zbiorze krawędzi, jedynka na przekątnej macierzy sąsiedztwa (w grafie nieskierowanym też istnieje ale na pewno trza inaczej definiować - tu jużeśmy się dogadali!), na rysunku też łatwo to zobaczyć, nieprawdaż? --Beaumont 21:53, 21 sie 2006 (CEST)

Chociaż nie może to nie był dobry przykład z tymi banknotami... Chwilowo zgupiałem i jadę poradzić się fachowca (jak to się odmienia przec płcie?) :). --Maciej "Nux" Jaros **zostaw notkę** 16:25, 21 sie 2006 (CEST)

Hm, nigdy nie wiesz z kim na wiki rozmawiasz... a może royas jest także niezłym fachowcem ? ;) A tak bardziej serio - daj znać o ewentualnych wynikach. --Beaumont 22:05, 21 sie 2006 (CEST)

Przez fachowca miałem na myśli matemtyczkę :). Jak zaczęła wchodzić na teorię mnogości, to przyznaję, że zacząłem się trochę gubić ;), ale w każdym razie wyszło na to, że rzeczywiście {v,v} jest formalnie zawarty w {v}. Jak by się chciało kombinować, to można ewentualnie zmienić {v,v} na {{v},{v}} i wtedy będzie się zgadzało, ale chyba nie ma potrzeby, bo pętla może być spokojnie zbiorem jednoelementowym {v}. Uporządkowanie natomiast także w jej opinii nie ma sensu. Przypomniała mi też, że tak naprawdę najlepszą definicją jest ta z funkcją gamma (wspominaną już wyżej), bo w sumie bardzo istotne jest to, że krawędź jest przyporządkowana do wierzchołków. No, ale obecna wersja jest chyba OK. A tak przy okazji, to mój przykład był nie bardzo, bo nie wziąłem pod uwagę, że to sytuacja, w której ten sam banknot (obiekt) stu złotowy mam dwa razy, a nie mam ich dwa :). --Maciej "Nux" Jaros **zostaw notkę** 02:41, 22 sie 2006 (CEST)

No cóż, a może royas jest również matemtykiem ? A tak serio, to oczywiście rozmowa może być pożyteczna (jak tutaj), ale przy okazji pamiętajmy że opinie fachowców, zwłaszcza anonimowych, nie są weryfikowalne i nie stanowią argumentu; opieramy się na źródłach i gdybym akurat miał jakieś pod ręką nie byłoby tej dyskusji. A tak robimy trochę po amatorsku - ale coś tam przynajmniej wychodzi ;) Pozdr. --Beaumont 09:41, 22 sie 2006 (CEST)

Bardziej czuję się informatykiem(uni), ale nie mam tego na piśmie ;) jeszcze. Myślę, że za parę dni uda mi się zerknąć do paru fachowych książek. royas 10:26, 22 sie 2006 (CEST)

no to wiemy jak się odmienia przez płcie fachowiec :) Czyli z pętlą mamy ustalone. Nie jestem przekonany czy {{v},{v}} by coś zmienił bo to to samo co { {v} }. Jeśli chodzi o definicję z gammą, to zostawiłbym ją w wariantach, ale przerobił z zbioru na trójkę - w literaturze stosuje się to wymiennie (zbiór jest mniej precyzyjny), a byłoby analogicznie jak w pierwszej definicji. No i jeszcze kwestia notacji czy krotki zapisujemy w "<>" (jak w krotka czy w "()" (jak np. w grupa (matematyka). Chociaż to pytanie trzebaby zadać na jakimś większym forum, bo fajnie by było żeby kiedyś to ujednolicić w całej wiki (przynajmniej działami).

trafna uwaga co do {{v},{v}}, zgoda co do reszty (definicja z gamą i notacja); pytanie na forum -ok, tylko gdzie? W źródłach nie ma tu zdaje się jednolitego podejścia i jest to trochę kwestia gustu; jak wybierzemy tak możemy ujednolicić. --Beaumont 12:16, 22 sie 2006 (CEST)

Chodziło mi o póżniejsze ujednolicane między artykułami. Ale to teraz nie jest istotne royas 13:32, 22 sie 2006 (CEST)

{ {v},{v} } to nie jest to samo co { {v} } - tu oszustwo ;) polega na tym, że te dwa zbiory można uznać za różne obiekty i wtedy pierwszy {v} jest różny od drugiego {v}. Tak przynajmniej to zrozumiałem. No, ale to rozważanie czysto akadamickie, bo nie widziałem nigdzie takiej reprezentacji. --Maciej "Nux" Jaros \\ zostaw notkę // 14:56, 22 sie 2006 (CEST)

Jak spojrzysz do wikipedii Inkluzja (matematyka) albo multizbiór albo na definicję równości zbiorów royasa powyżej, to może jeszcze zmienisz zdanie ;) No chyba że w wyższej teorii logiki są lepsze subtelności (wtedy jednak nazwać je po imieniu i źródle). I zgoda, że nie ma tu o co się spierać bo artykułowi to niepotrzebne. Pozd --Beaumont 16:18, 22 sie 2006 (CEST).

To podstawmy {v}=a wtedy mamy { {v},{v} }={a,a}={a} co zgdnie z założeniem ={ {v} } :) Po prostu nie można {v} traktować jak coś innego od {v}, bo mówimy tu o zbiorach matematycznych, a nie informatycznych. Gdyby {v} mogło być czymś innym od {v} to zbiór potęgowy możnaby napompować w nieskończoność. :) A tak nie jest. No ale faktycznie teraz nie ma to znaczenia dla tego art.

[edytuj] Wstęp

Trochę przerobiłem ten wstęp. Wydaje mi się zbyt ogólnikowy i w sumie większości to trochę takie, przepraszam za wyrażenie, "lanie wody", ale szkoda mi było kasować, bo w sumie ktoś się przy tym napracował. Dlatego ciągle liczyłem na to, że zmieni autor. --Maciej "Nux" Jaros **zostaw notkę** 05:33, 21 sie 2006 (CEST).

[edytuj] Grafy, reprezentacje, izomorfizy

Zacznę od tego, że w tym artykule w sekcji o izomofizmie grafów dosyć dużo jest o ich graficznej reprezentacji, natomiast w izomorfizm grafów nic o tym nie ma. Z pierwszej definicji wynika m. in., że grafy różniące się tylko ich reprezentacją, są izomorficzne. A tak naprawde (zgodnie ze wszystkimi zaprezentowanymi definicjami grafów, są to te same grafy, czy też raczej jest to ten sam graf, więc tak naprawdę to ciężko nawet mówić, że on/one(?) się czymś różnią. Różnią się jego reprezentacje. Więc tu należałoby usunąć wszystkie wzmianki o reprezentacji grafu.

Z drugiej strony są jednak miejsca gdzie przez graf rozumie się konkretną reprezentację graficzną (graf płaski, ściana, konstrukcja grafu dualnet) i dlatego możliwe, że trzeba o tym jakoś napisać. No i jeszcze pojawiło się gdzieś pojęcie izomorficzne przedstawienie.

Do literatury narazie nie mam dostępu. Gdyby ktoś miał i sprawdził pod tym kątem... royas 13:32, 22 sie 2006 (CEST)

Różnica polega tylko na tym, że zmieniane są etykiety wierzchołków, więc są to prawie te same grafy, ale nie są te same (dokładnie nie muszą być te same). Zobacz też w artykule głównym :). --Maciej "Nux" Jaros \\ zostaw notkę // 01:00, 24 sie 2006 (CEST)

[edytuj] Wycofane zmiany notacji

Zmiany zostały cofnięte poniważ ich autor nie przedstawił żadnych źródeł, na których oparł swoje modyfikacje. Uprzednia treść artykułu była efektem pracy wielu osób korzystających przy tym z fachowej literatury. Nowe modyfikacje nie zostały w ten sposób zweryfikowane. Superborsuk ^Ω 23:46, 25 gru 2006 (CET)

Uzasadnienie potrzeby modyfikacji artykułu zgodnie z zasadą weryfikowalności leży po stronie osoby ją proponującej, ale ze względu na nalegania autora postanowiłem wypunktować błędy oraz nieścisłości w wycofanej edycji:

Oznaczenie pary uporządkowanej <V,E> jest zgodne z definicją, która została zaproponowana przez Kuratowskiego,
Oznaczenie (V,E) zastosowano w
- Graf dwudzielny - tu trzeba się zastanowić, ale sądzę że dla trójki uporządkowanej też powinno być podobnie, nad tą definicją trzeba popracować
- Twierdzenie o kojarzeniu małżeństw
- Graf skierowany - to mój błąd powstały podczas przeniesienia treści z graf kiedy oznaczenie było jeszcze niepoprawne, poprawiłem

Niektóre modyfikacje stylistyczne wprowadzają błędne informacje:

Graf – to - w uproszczeniu - zbiór wierzchołków połączonych...

Tu nie ma żadnego uproszczenia. Zbiór stanowi podstawowe pojęcie teorii mnogości, a krawędź pojawia się w wielu działach matematyki. Definicja zawsze odnosi się do pewnych aksjomatów. Powinniśmy się trzymać ścisłego języka matematyki, gdzie pojęcie "uproszczenia" w tym sensie nie istnieje.

Nie twierdzę, że ani jedna zmiana nie jest poprawna lub neutralna. Niestety autor wprowadził wiele znaczących zmian i szereg drobnych przez jedną edycję. Nie podważam potrzeby pracy nad artykułem, ale sądzę, że tak zasadnicze zmiany wymagają uzasadnienia oraz podania źródeł. Gdyby te same zmiany wprowadzono z podaniem polskiej literatury źródłowej moja opinia byłaby zupełnie inna, bo wiem że notacja stosowana przez różnych autorów bywa odmienna.

W angielskiej Wikipedii hasło en:Graph (mathematics) stosuje oznaczenie pary z nawiasami. Jednak w polskiej szkole matematycznej w wielu przypadkach używane jest oznaczenie z nawiasami ostrymi. Sądzę, że powinniśmy w polskiej Wikipedii zachowywać lokalny charakter pewnych artykułów mających związek z naszą kulturą. Różnice w oznaczeniach grafów są wyrazem takich odmienności w języku matematyki. Polskie słowa całka czy pochodna też odbiegają swoimi źródłami od terminów stosowanych na całym świecie. Powinniśmy uszanować dorobek polskich matematyków na tym polu, stosując stworzoną przez nich notację.

Superborsuk ^Ω 02:13, 26 gru 2006 (CET)

Niestety, nie mogę się zgodzić się z powyższą argumentacją.

Jak już napisałem na stronie dyskusji Superborsuka, nie mam nic przeciwko konsekwentnemu stosowaniu notacji <x,y>. Po wycofaniu mojej edycji nadal występuje raz <x,y> raz (x,y).
Chciałem ponadto zauważyć, że absolutna większość artykułów na Wiki używa notacji (x,y) (mogę zrobić listę jeżeli potrzeba). O ile Polacy nie gęsi i swoje całki mają, to notacja matematyczna jest międzynarodowa. Poza tym, w graf skierowany przed zamianą notacji było używane (x,y) a po zamianie jest używane niekonsekwentnie raz <x,y> raz (x,y). Wszystkie linki z graf (matematyka) prowadzą do artykułów z notacją (x,y) oprócz 5 - graf skierowany, iloczyn kartezjański, droga (teoria grafów), para uporządkowana oraz graf symetryczny. Przy czym tylko w dwóch ostatnich notacja <x,y> jest niemieszana z (x,y). Wszystkie pozostałe linki, jak również absolutna większość kat. matematyka używa (x,y). Nawet gdyby już ustalono <x,y> (a tego jakoś nigdzie nie widzę, ani tutaj ani na stronie dyskusji medalu) to nie ma to najmniejszego związku z weryfikowalnością, ale z konsensusem i przyjętymi umowami na Wikipedii, nie w literaturze.
Graf to tylko w uproszczeniu zbiór wierzchołków połączonych krawędziami. To tak jak mówić "grupa to zbiór w którym określono działanie mające pewne własności". W teorii mnogości zawsze abstrahuje się od natury elementów zbioru i od związków między nimi. To oznacza, że {1,2,3} jest zbiorem tak samo "interesującym" jak {1,7,100} czy też {x,y,z}, mimo że w pierwszym zbiorze widać jakąś zależność pomiędzy elementami. "Coś" zawierające 1, 2, 3 w którym połączono 1 i 2 zbiorem już nie jest. Albo "zbiór wierzchołków" albo "zbiór krawędzi" ale nie "zbiór wierzchołków połączonych krawędziami", gdyż w zbiorze możemy określić tylko należenie, a nie łączenie elementów krawędzią. Formalnie: dwa zbiory są równe gdy należą do nich te same elementy. Mamy relację "należenia" lecz nie ma relacji "połączenia" dwóch elementów zbioru. Można mówić o "zbiorze wierzchołków", o "zbiorze krawędzi" ale nie o "zbiorze wierzchołków połączonych krawędziami", gdyż nie ma takiego czegoś w języku matematycznym jak "wierzchołki połączone krawędziami".
Jeżeli już koniecznie chcemy rozumieć graf jako zbiór, to z definicji G:=<V,E> czy też G:=(V,E) oraz def. Kuratowskiego mamy G = {{V},{V,E}}, czyli: graf jest zbiorem zawierającym (zbiór złożony ze zbioru wierzchołków) oraz (zbiór złożony ze zbioru wierzchołków i zbioru krawędzi).

googl d 13:40, 26 gru 2006 (CET)

Jeżeli nie będzie merytorycznych sprzeciwów zmiany przywrócę za kilka dni. googl d 19:26, 2 sty 2007 (CET)

Z tymi ścisłymi definicjami to jest tak: traktując rzecz czysto formalnie, większość pojęć matematycznych można zdefiniować na różne sposoby, uzyskując struktury formalnie różne, jednak izomorficzne. A matematycy i tak muszą sobie przekodować te formalne definicje na nieformalne ich rozumienie, bo inaczej by nie mogli pracować. Oczywiście muszą często schodzić na poziom formalny, ale to, którą z izomorficznych definicji wybiorą to już sprawa wygody konkretnego zastosowania. Trudno więc powiedzieć, czy ważniejsza jest formalna definicja, czy jej zdroworozsądkowe tłumaczenie. Chyba jednak obydwa są ważne...

Graf jako "zbiór wierzchołków połączonych krawędziami" nie jest formalnie rzecz biorąc w ogóle definicją matematyczną, aczkolwiek nieformalnie chyba mówi więcej niż definicja przez parę (V,E). Najlepiej byłoby chyba umieścić ją jako "intuicyjne rozumienie pojęcia grafu", a obok podać jedną z możliwych formalnych definicji. Ogólnie jednak, skoro już miałbym wybierać z tych dwóch to wersja Googla wydaje mi się sensowniejsza.

Uważam też, że w większości przypadków na wikipedii używana jest dla pary notacja (a,b) a nie <a,b>, więc dobrze byłoby to ujednolicić. Olaf _D 19:45, 2 sty 2007 (CET)

Ktoś napisał wyżej, że notacja matematyczna jest międzynarodowa. Nie jest to prawdą, notacja nie jest ustalona w żaden sposób, nie ma w tej kwestii międzynarodowych standardów. I prawdę mówiąc - nie są one potrzebne. Wszystko zależy od chwili, przyzwyczajeń, wygody, pogody za oknem, etc.
Nie wydaje mi się dobrym pomysłem wybór notacji na podstawie ilości artykułów ją używających - liczba ta może okazać się wcale nieadekwatna do ilości osób ją stosujących.
Z własnego doświadczenia wiem, że notacja (x,y) na oznaczenie pary jest używana w Krakowie (jeżeli na dodatek okaże się że tylko na jednej uczelni to będzie śmiesznie ;) ), natomiast <x,y> jest stosowana we Wrocławiu i Warszawie. Osobiście jestem za notacją <x,y>, ale chyba powinno być jakieś głosowanie (z większą liczbą uczestników, może z portalu:matematyka lub matematyka.org?). Dreamer_ 22:38, 7 sty 2007 (CET)

"Międzynarodowa" = używana na całym świecie, niekoniecznie regulowana przez jakąś umowę. Nie mówię że istnieją jakieś konwencje. Ale takie zapisy jak $e x$ lub $i 2 = - 1$ są rozpoznawalne chyba w większości świata.

Co do notacji, zgadzam się że nie powinno się jej wybierać na podstawie ilości artykułów, nie wiem jak to wygląda na poszczególnych uczelniach. Ale chodziło mi o to, że nie można uzasadniać notacji <a,b> jej "polskością". Jedni piszą tak, drudzy inaczej, zmieniłem na jedną dla konsekwencji. Cytując siebie: "nie mam nic przeciwko konsekwentnemu' stosowaniu notacji <x,y>". Pozdr., googl d 00:03, 27 sie 2007 (CEST)

[edytuj] Wiele krawędzi pomiędzy tymi samymi wierzchołkami

Grafy zdefiniowane tak jak tutaj mogą mieć co najwyżej jedną krawędź pomiędzy tymi samymi wierzchołkami (skierowane - najwyżej dwie w przeciwne strony). Wydaje mi się, że rozważa się też grafy, w których może ich być więcej. Olaf @ 00:09, 9 cze 2007 (CEST)

Czasem się rozważa i jest to ujęte w "warianty definicji". royas 08:03, 9 cze 2007 (CEST)

Faktycznie, nie doczytałem. Dzięki. Olaf @ 10:35, 9 cze 2007 (CEST)

[edytuj] Graf (matematyka)

Artykuł zgłoszony przez Rnm, 24 kwietnia 2006.

~~artykuł jeszcze nie na medal, ale chyba już niewiele brakuje (trochę więcej rysunkowych przykładów, "bardziej po polskiemu" niektóre zdania) Rnm 15:11, 24 kwi 2006 (CEST)~~ poprawiłem, cieszę się z tego jednego głosu aprobaty ;), jeszcze nie jest perfekt, jakbyście mogli jakieś uwagi dać, czego braku, co nie tak ipt., bo ja osobiście zaczynam tracić perspektywę ;) Rnm 13:54, 28 kwi 2006 (CEST)

Martixx ^Dyskusja 09:33, 23 sie 2007 (CEST) 12:38, 28 kwi 2006 (CEST)
Witek52 dyskusja @ 19:32, 3 maja 2006 (CEST)

Przeciw

4^@ 15:40, 12 maja 2006 (CEST). Literówki, interpunkcja, styl. Nie rozumiem dlaczego definicje powtarzają się dwukrotnie - raz formalnie, raz nieformalnie. To samo z klasami grafów. W chwili obecnej artykuł nadaje się wyłącznie DoPracowania.
przeciw Nux ^>dyskusja< 10:36, 13 maja 2006 (CEST)

dyskusja

Po dość pobieżnym przejrzeniu artykułu wydaje mi się, że jest w nim "jescze trochę chaosu". Następujące kwestie wydają się wymagać uporządkowania: definicje (jest ich za dużo i jakoś nie w jednym miejscu), ~~kwestia planarności (trochę są pomieszane sprawy dotyczące tylko grafów planarnych i ogólnych)~~. Brakujące rzeczy: operacje na grafach (zob. Operations_on_graphs), ważne twierdzenia dotyczące grafów, uogólnienia ... Prawdopodobnie należałoby to jakoś podzielić. Być może łatwiej byłoby dorobić się medalu, mając dobry artykuł Teoria grafów. Kuszi 22:08, 3 maja 2006 (CEST).

Nie wiem co tam robią te rysunki na początku. Graf formalnie nie ma gdzieś przyszpilonych wierchołków (nie muszą zachowywać odległości między sobą), więc siatka nie jest grafem. Można reprezentować pewne połączenia w figurze jako graf, ale sama siatka nie jest grafem, bo w siatce ważne są odległości między wierzchołkami. Schemat blokowy też nie jest formalnie grafem. Graf to coś z wierchołkami, krawędziami i w zasadzie tyle (jeszcze czasem jakieś wagi krawędzi). W grafie nie ma rodzajów wierzchołków, ani ich jakiś szczegółowych opisów. Tak samo jak siatką można go natomiast uprościć do grafu tracą część (w tym wypadku sporą) informacji. Osobiście nie specjalnie widzę celowość takiego działania, ale domyślam się, że chodziło komuś może raczej o jakiś diagram przepływów.

Generalnie cały wstępny opis jest mocno nieformalny i miesza trochę grafy z diagramami. Ponadto przychylam się do tego, że może warto byłoby część informacji przenieść do teorii grafów. Natomiast w tym artykule widziałbym raczej spis/opis rodzajów grafów itp.

Nux ^>dyskusja< 10:36, 13 maja 2006 (CEST)

buła - wszystkie te rzeczy są grafami, a to, że w siatce są takie a nie inne wymagania nic nie zmienia.

Schemat blokowy jest jak najbardziej grafem - są wierzchołki (instrukcje), są krawędzie (przebieg programu) i tyle!

Zresztą, przykłady te nie są wzięte z sufitu, pojawiają się w wielu książkach o teorii grafów

Na samym wstępie jest napisane - graf to zbiór wierzchołków połączonych krawędziami..

Nie rozumiem dlaczego definicje powtarzają się dwukrotnie - raz formalnie, raz nieformalnie

bo nieformalna przedstawia samą idee, formalna jest "matematyczna" i przydaje się w np. "formalnych" dowodach..

Rnm 21:08, 13 maja 2006 (CEST)

Wyjaśniam dlaczego według mnie nie jest tak jak piszesz:

Graf = krawędzie + wierzchołki (ew. wagi)
Siatka = Graf + stałe odległości między wierchołkami + kąty między krawędziami
Schemat blokowy = Graf + opis wierchołków + różne funkcje wierchołków

Innymi słowy do pewnych celów można uprościć zarówno schemat, jak i siatkę do grafu, ale to nie jest to samo. Podobnie jak prostokąt to nie jest to samo co kwadrat. A za błedy w podręcznikach nie odpowiadam ;).

Nux ^>dyskusja< 03:02, 14 maja 2006 (CEST)

Powinniśmy sie zastanowić czy artykułem głównym dotyczącym tematyki grafów powinien być graf (matematyka) czy teoria grafów. Kiedy przeciętny czytelnik będzie chciał się czegoś dowiedzieć o grafach, to z czystego lenistwa wpisze hasło graf i z disambiguation trafi do graf (matematyka). Zgodnie z tym tokiem rozumowania informacje podstawowe powinny znajdować się w haśle graf. Teoria grafów to hasło, do którego trafi z pewnością bardziej oczytana osoba i moim zdaniem powinno ono być najwyżej spisem treści najważniejszych zagadnień tej dziedziny wiedzy.

Co do nadmiaru definicji matematycznych to zastanawiam się, czy ze względu na ich bogactwo nie powinniśmy stworzyć hasła definicja grafu, w którym je wszystkie dogłębnie opiszemy. Niestety co autor, to nieco inne podejście do tego problemu, więc możliwe będzie opisanie różnych wariantów tych definicji. W artykule graf (matematyka) powinniśmy moim zdaniem pozostawić tylko skrótowy opis tego zagadnienia.

Na koniec problem diagramów. W polskiej Wikipedii diagram jest zdefiniowany jako graficzna reprezentacja pewnych idei. Graf jest abstrakcyjnym bytem, który kryje się z mózgach matematyków. Nie można go zobaczyć, dotknąć i powąchać. Kiedy matematyk "rysuje graf", oznacza to, że tworzy na kartce reprezentujący go diagram. Diagram tak samo ma się do grafu jak znak 2 to abstrakcyjnej idei liczby dwa. Superborsuk ^Ω 04:40, 16 maja 2006 (CEST)

Niekażdy diagram jest grafem (czy też reprezentacją grafu), ale poza tym w zasadzie zgoda (to znaczy większość formalnych definicji może pójść do teorii, albo definicja grafu, czy coś). Prosiłbym tylko o przeredagowanie (ja nie wyrabiam) tego wstępu, żeby był trochę mniej dowolny. Nux ^>dyskusja< 13:36, 20 maja 2006 (CEST)

Wydaje mi się, że w formalnej definicji jest błąd, więcej w dyskusji artykułu. royas 03:05, 12 sie 2006 (CEST)

Źródło: "http://pl.wikipedia.org/wiki/Dyskusja:Graf_%28matematyka%29"