• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Teoria grafów

    Przeczytaj także...
    Analiza sieciowa lub społeczna analiza sieciowa (ang. social network analysis) to określenie badań sieci społecznej i stosunków społecznych. Badania te wykorzystują teorię sieci (ang. network theory) i koncentrują się na analizie stosunków pomiędzy elementami sieci (jednostkami, organizacjami, itp.).Skojarzeniem grafu nazywa się niezawierający pętli podzbiór krawędzi grafu (ozn. M) taki, że każdy wierzchołek jest końcem co najwyżej jednej krawędzi z M, tj. każdy wierzchołek jest połączony krawędzią z dokładnie jednym innym wierzchołkiem albo wcale.
    Kolorowanie grafu polega w ogólności na przypisaniu określonym elementom składowym grafu (najczęściej wierzchołkom, rzadziej krawędziom lub ścianom) wybranych kolorów według ściśle określonych reguł. Klasyczne (czyli wierzchołkowe) kolorowanie grafu jest związane z przypisaniem wszystkim wierzchołkom w grafie jednej z wybranych barw w ten sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Innymi słowy, pewne pokolorowanie wierzchołkowe jest poprawne (legalne, dozwolone) wtedy, gdy końcom żadnej krawędzi nie przypisano tego samego koloru.

    Teoria grafów to dział matematyki i informatyki zajmujący się badaniem własności grafów. Informatyka rozwija także algorytmy wyznaczające pewne właściwości grafów. Algorytmy te stosuje się do rozwiązywania wielu zadań praktycznych, często w dziedzinach na pozór nie związanych z grafami.

    Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków (ilustracja po prawej stronie). Grafy to podstawowy obiekt rozważań teorii grafów. Za pierwszego teoretyka i badacza grafów uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich.Algorytm najbliższego sąsiada – zachłanny algorytm rozwiązywania problemu komiwojażera polegający na odwiedzaniu, począwszy od wybranego wierzchołka, wierzchołka znajdującego się najbliżej wierzchołka ostatnio odwiedzonego. Bardzo prosty do zaprogramowania, szybki, ale daje słabe wyniki.

    Opis zagadnienia mostów królewieckich opublikowany w 1736 roku przez Leonharda Eulera jest uznawany za pierwszą pracę na temat teorii grafów.

    Algorytm Dijkstry, opracowany przez holenderskiego informatyka Edsgera Dijkstrę, służy do znajdowania najkrótszej ścieżki z pojedynczego źródła w grafie o nieujemnych wagach krawędzi.Izomorfizm grafów – Grafy G jest izomorficzny z grafem F, jeśli istnieje takie, różnowartościowe i na, przyporządkowanie (bijekcja) wierzchołków grafu H wierzchołkom grafu G , że jeśli jakieś dwa wierzchołki są połączone krawędzią w jednym z grafów, to odpowiadające im wierzchołki w drugim grafie również łączy krawędź.

    Zagadnienia teorii grafów[]

  • kolorowanie grafów
  • twierdzenie o czterech barwach
  • problem znajdowania drogi
  • minimalne drzewo rozpinające
  • problem najkrótszej ścieżki PERT CPM
  • problem komiwojażera
  • problem rekonstrukcji
  • zagadnienienia związane z sieciami przepływowymi, maksymalny przepływ
  • zbiór dominujący
  • ekstremalna teoria grafów
  • liczby Ramseya
  • skojarzenie
  • izomorfizm grafów
  • grafy losowe
  • prawdopodobieństwo spójności grafu losowego (drzewa losowego)
  • komputerowa reprezentacja grafów
  • problem chińskiego listonosza
  • Ważne algorytmy[]

  • algorytm Bellmana-Forda
  • algorytm Dijkstry
  • algorytm Floyda-Warshalla
  • algorytm Johnsona
  • algorytm Kruskala
  • algorytm Prima
  • algorytm najbliższego sąsiada
  • Zobacz też[]

  • graf
  • programowanie sieciowe
  • analiza sieciowa
  • Programowanie sieciowe to przedstawienie problemu w postaci grafu, a następnie analizowanie takiego grafu przy zastosowaniu teorii grafów.Minimalne drzewo rozpinające (ang. MST, Minimum Spanning Tree) – drzewo rozpinające danego grafu o najmniejszej z możliwych wag, tj. takie, że nie istnieje dla tego grafu inne drzewo rozpinające o mniejszej sumie wag krawędzi.



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Warto wiedzieć że... beta

    Algorytm Kruskala wyznacza minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego.
    Reprezentacja grafu to sposób zapisu grafu umożliwiający jego obróbkę z użyciem programów komputerowych. Dwa najpopularniejsze sposoby zapisu informatycznego grafów to macierz sąsiedztwa oraz listy sąsiedztwa.
    PERT (ang. Program Evaluation and Review Technique) – probabilistyczna metoda planowania i kontroli projektu, wykorzystująca programowanie sieciowe, stosowana w zarządzaniu projektami.
    Sieć przepływowa G ( V , E ) {displaystyle G(V,E)} – graf skierowany, w którym każda krawędź ( u , v ) {displaystyle (u,v)} należąca do zbioru krawędzi E {displaystyle E} ma nieujemną przepustowość c ( u , v ) ⩾ 0 {displaystyle c(u,v)geqslant 0} . W sieci wyróżniamy dwa wierzchołki: źródło s {displaystyle s} i ujście t {displaystyle t} .
    Informatyka – dyscyplina nauki zaliczana do nauk ścisłych oraz techniki zajmująca się przetwarzaniem informacji, w tym również technologiami przetwarzania informacji oraz technologiami wytwarzania systemów przetwarzających informację. Początkowo stanowiła część matematyki, później rozwinęła się do odrębnej dyscypliny – pozostaje jednak nadal w ścisłej relacji z matematyką, która dostarcza informatyce podstaw teoretycznych.
    Zagadnienie mostów królewieckich − problem, nad którym rzekomo głowili się mieszkańcy Królewca, a który rozwiązał w XVIII wieku Leonhard Euler.
    Problem komiwojażera (TSP - ang. travelling salesman problem) jest to zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.

    Reklama

    Czas generowania strony: 0.01 sek.