• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Graf - matematyka



    Podstrony: 1 [2] [3] [4] [5] [6]
    Przeczytaj także...
    Kodowanie Huffmana (ang. Huffman coding) – jedna z najprostszych i łatwych w implementacji metod kompresji bezstratnej. Została opracowana w 1952 roku przez Amerykanina Davida Huffmana.Macierz sąsiedztwa (multi)grafu G {displaystyle G} – macierz kwadratowa, w której aij oznacza liczbę krawędzi pomiędzy wierzchołkami i {displaystyle i} i j {displaystyle j} . W przypadku grafów prostych macierz sąsiedztwa jest macierzą zerojedynkową z zerami na głównej przekątnej. Dla grafów nieskierowanych macierz sąsiedztwa jest z definicji symetryczna.

    Graf – podstawowy obiekt rozważań teorii grafów, struktura matematyczna służąca do przedstawiania i badania relacji między obiektami. W uproszczeniu graf to 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.

    Wierzchołki grafu mogą być numerowane i czasem stanowią reprezentację jakichś obiektów, natomiast krawędzie mogą wówczas obrazować relacje między takimi obiektami. Wierzchołki należące do krawędzi nazywane są jej końcami. Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie nazywany jest grafem skierowanym lub orgrafem. Krawędź grafu może posiadać wagę, to znaczy przypisaną liczbę, która określa, na przykład, odległość między wierzchołkami (jeśli np. graf jest reprezentacją połączeń między miastami). W grafie skierowanym wagi mogą być zależne od kierunku przechodzenia przez krawędź (np. jeśli graf reprezentuje trud poruszania się po jakimś terenie, to droga pod górkę będzie miała przypisaną większą wagę niż z górki).

    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.Algebra Boole’a – algebra ogólna stosowana w matematyce, informatyce teoretycznej oraz elektronice cyfrowej. Jej nazwa pochodzi od nazwiska matematyka, filozofa i logika George’a Boole’a. Teoria algebr Boole’a jest działem matematyki na pograniczu teorii częściowego porządku, algebry, logiki matematycznej i topologii.

    Za pierwszego teoretyka i badacza grafów uważa się szwajcarskiego matematyka i fizyka Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich. Pierwsze użycie określenia „graf” przypisywane jest Jamesowi Josephowi Sylvesterowi – matematykowi angielskiego pochodzenia.

    Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.Wielka Brytania, Zjednoczone Królestwo (ang. United Kingdom), Zjednoczone Królestwo Wielkiej Brytanii i Irlandii Północnej (ang. United Kingdom of Great Britain and Northern Ireland) – unitarne państwo wyspiarskie położone w Europie Zachodniej. W skład Wielkiej Brytanii wchodzą: Anglia, Walia i Szkocja położone na wyspie Wielka Brytania oraz Irlandia Północna leżąca w północnej części wyspy Irlandia. Na wyspie tej znajduje się jedyna granica lądowa Zjednoczonego Królestwa z innym państwem – Irlandią. Poza nią, Wielka Brytania otoczona jest przez Ocean Atlantycki na zachodzie i północy, Morze Północne na wschodzie, kanał La Manche na południu i Morze Irlandzkie na zachodzie.

    Spis treści

  • 1 Zastosowanie grafów
  • 2 Definicje
  • 2.1 Graf
  • 2.2 Graf skierowany
  • 2.3 Graf mieszany
  • 2.4 Grafy z wagami
  • 2.5 Warianty definicji
  • 3 Inne typy grafów
  • 3.1 Grafy nieskończone
  • 3.2 Graf abstrakcyjny
  • 3.3 Graf geometryczny
  • 4 Pojęcia służące do opisu grafów
  • 4.1 Alfabetyczna lista definicji
  • 4.2 Oznaczenia formalne
  • 4.3 Izomorfizm i homeomorfizm grafów
  • 4.4 Klasy grafów
  • 5 Operacje na grafach
  • 5.1 Operacje binarne
  • 5.2 Operacje unarne
  • 6 Algorytmy grafowe
  • 6.1 Przeszukiwanie grafu
  • 7 Sposoby prezentacji grafów
  • 7.1 Rysunek grafu
  • 7.2 Macierz sąsiedztwa
  • 7.3 Lista sąsiedztwa
  • 7.4 Macierz incydencji
  • 8 Uogólnienia
  • 9 Zobacz też
  • 10 Przypisy
  • 11 Bibliografia
  • 12 Linki zewnętrzne
  • Stopień wierzchołka w grafie to liczba krawędzi 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.Mając graf planarny G można zdefiniować dla niego pojęcie grafu dualnego G*. Termin dualny (ang. dual) jest użyty ponieważ dualność jest symetryczna, jeśli graf X jest dualnym grafem grafu Y, to graf Y jest dualnym grafem grafu X; w efekcie grafy takie są podawane jako pary.

    Zastosowanie grafów[]

    Zastosowanie grafów
    Drzewo binarne
    Niedeterministyczny automat skończony
    Graficzne przedstawienie cząsteczki propanu

    Za najstarszy przykład zastosowania grafów w rozwiązaniu zadanego problemu uznaje się zagadnienie mostów królewieckich, opis którego opublikował w 1736 roku Leonhard Euler:

    Przestrzeń metryczna – zbiór z zadaną na nim metryką, tj. funkcją, która określa odległość między każdą parą elementów tego zbioru.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.

    Konigsberg bridges.png7 bridges.svgKönigsberg graph.png

    Grafy mogą służyć do praktycznych zastosowań (także z pomocą komputerów) w wielu różnorodnych problemach, np.: sieć dróg z wierzchołkami reprezentującymi skrzyżowania i krawędziami przedstawiającymi ulice, sieć pomieszczeń i korytarzy w budynkach, dzięki czemu możliwe jest komputerowe wynajdywanie najlepszej drogi ze swojego obecnego położenia do pożądanego celu. Algorytmy grafowe stanowią istotną część programów obsługujących urządzenia GPS. System sztucznej inteligencji w niektórych grach komputerowych musi odszukać dla sterowanych przez program postaci najlepszą drogę, która pozwoli zaatakować przeciwnika. Zagadnienie to może być rozwiązane w oparciu o własności grafów. Przedstawienie w formie grafów sieci komputerowych pozwala na stworzenie oprogramowania usprawniającego trasowanie w Internecie. W dużych organizacjach realizację zlecanych przez klientów zadań można przedstawić w postaci grafów, dzięki czemu możliwe jest zwiększenie wydajności: wierzchołki mogą reprezentować pracowników, a krawędzie grafu – przepływ zadań. Za pomocą związanych z grafami pojęć można opisywać też m.in. rysunki obwodów, schematy blokowe, ponieważ przedstawiają one połączenia lub relacje, zachodzące między różnymi fragmentami wykresu.

    Wykres – graficzna forma przedstawienia zmienności zjawiska, procesu, wielkości, zależności lub jakichkolwiek danych. Zwykle przedstawiany w dwóch wymiarach, ale może być wielowymiarowy.Graf planarny – graf, który można narysować na płaszczyźnie tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności nazywane jest jego rysunkiem płaskim. Graf planarny o zbiorze wierzchołków i krawędzi zdefiniowanym poprzez rysunek płaski nazywany jest grafem płaskim.

    Drzewa grafowe przydatne są w praktycznej reprezentacji różnego rodzaju hierarchii. Mistrzostwa sportowe czy drzewo genealogiczne mogą być w przejrzysty sposób opisane przez drzewa binarne. Do tworzenia kodów Huffmana można wykorzystać drzewa binarne z wagami. Idea działania danego niedeterministycznego automatu skończonego może być w przejrzysty sposób pokazana przez odpowiedni graf.

    P2P (ang.) Peer-to-Peer – model komunikacji w sieci komputerowej, zapewniający wszystkim hostom te same uprawnienia, w odróżnieniu od architektury klient-serwer.Asymptotyczne tempo wzrostu jest miarą określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Stosowane jest szczególnie często w teorii obliczeń, w celu opisu złożoności obliczeniowej, czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu. Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.

    Wzrasta również znaczenie i wykorzystanie teorii grafów w dziedzinach takich, jak chemia, lingwistyka, geografia, architektura i inne.

    Podstrony: 1 [2] [3] [4] [5] [6]



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

    Warto wiedzieć że... beta

    Komputer (z ang. computer od łac. computare – liczyć, sumować; dawne nazwy używane w Polsce: mózg elektronowy, elektroniczna maszyna cyfrowa, maszyna matematyczna) – maszyna elektroniczna przeznaczona do przetwarzania informacji, które da się zapisać w formie ciągu cyfr albo sygnału ciągłego.
    Kazimierz Kuratowski (ur. 2 lutego 1896 w Warszawie, zm. 18 czerwca 1980 w Warszawie), polski matematyk, jeden z czołowych przedstawicieli warszawskiej szkoły matematycznej.
    Las - graf, którego każdy spójny podgraf jest drzewem. Równoważnie można zdefiniować las po prostu jako acykliczny graf nieskierowany (czyli nie zawierający żadnych cykli). Wtedy jego spójne składowe są drzewami.
    Alfabet łaciński, łacinka, alfabet rzymski – alfabet, system znaków służących do zapisu większości języków europejskich oraz wielu innych. Jest najbardziej rozpowszechnionym alfabetem na świecie – posługuje się nim ok. 35% ludzkości. Wywodzi się z systemu służącego do zapisu łaciny.
    W językach programowania pozwalających na bezpośredni dostęp do pamięci (jak np. asembler, C, C++, Cyclone) pamięć jest reprezentowana jako jednowymiarowa tablica bajtów - wszystkie zmienne (statyczne i dynamiczne) są umieszczane w tej „tablicy”.
    Struktura danych (ang. data structure) - sposób uporządkowania informacji w komputerze. Na strukturach danych operują algorytmy.
    Turniej to graf skierowany w którym każde dwa wierzchołki są połączone dokładnie jedną skierowaną krawędzią. Jest to skierowany odpowiednik grafu pełnego.

    Reklama