|
Definicja Teoria grafów (Szukaj)
|
Teoria grafów to dział matematykiMatematyka była niegdyś rozumiana jako nauka o liczbach (arytmetyka) i figurach (bryłach) geometrycznych (geometria). Do dziś w popularnych encyklopediach określana jest jako nauka o wielkościach, czyli o stosunkach ilościowych i formach przestrzennych. Z biegiem czasu dodano również do obszaru zainteresowań matematyki wszystko, co wiąże się z pojęciem granicy....
Graf jest definiowany jako zbiór punktów (zwanych wierzchołkami lub węzłami) połączonych krawędziami (które czasem nazywa się też łukami). Bardziej formalnie, graf prosty to zbiór wierzchołków V i zbiór E nieuporządkowanych par różnych elementów zbioru V zwany zbiorem krawędzi. Przykład grafu o sześciu wierzchołkach oraz siedmiu krawędziach:
W tym przypadku V = {1, 2, 3, 4, 5, 6} a E = {(1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6)}. Graf prosty o n wierzchołkach można także opisać (z dokładnością do izomorfizmu) za pomocą symetrycznej macierzy kwadratowej A = [aij], gdzie i,j = 1,...,n, w ten sposób, że aks = 1, gdy wierzchołki o numerach k i s są połączone krawędzią, w przeciwnym przypadku aks = 0. Dla przykładu, graf z powyższego rysunku może być przedstawiony za pomocą następującej macierzy:
PojęciaSąsiad: Dwa wierzchołki są sąsiadami, jeśli istnieje krawędź pomiędzy nimi. W powyższym grafie wierzchołki 1 i 2 sąsiadują ze sobą, ale na przykład 2 i 4 już nie. Stopień wierzchołka: Stopień wierzchołka to liczba jego sąsiadów. W powyższym grafie wierzchołki 1 i 3 mają stopień 2, wierzchołki 2, 4 i 5 mają stopień 3, zaś wierzchołek 6 ma stopień 1. Suma stopni wszystkich wierzchołków jest równa podwojonej liczbie krawędzi grafu. Ścieżka: Ciąg wierzchołków, w którym każdy wierzchołek jest sąsiadem zarówno poprzedniego, jak i następnego. Ścieżkę uważa się za prostą, jeśli żaden z wierzchołków ścieżki nie powtarza się. W powyższym grafie {1, 2, 5, 1, 2, 3} jest ścieżką, a {5, 2, 1} jest ścieżką prostą. Jeśli od każdego wierzchołka grafu istnieje ścieżka do dowolnego innego, to graf jest spójny. Cykl: Jest to ścieżka, która zaczyna się i kończy w tym samym wierzchołku. W powyższym grafie {1, 5, 2, 1} jest jedynym cyklem długości 3. Drzewo: Jest to graf spójny bez cykli. Równoważnie: drzewo o n wierzchołkach to graf spójny o dokładnie n - 1 krawędziach. Drzewa są używane jako struktury danychStruktura danych (ang. data structure) - sposób uporządkowania informacji w komputerze. Na strukturach danych operują algorytmy. Przykładowe struktury danych to: rekord, zwany w niektórych językach po prostu strukturą (ang. struct, record), logiczny odpowiednik to krotka tablica lista drzewo i jego liczne odmiany (np. drzewo binarne) stos kolejka Podczas implementacji programu programista często staje przed wyborem między różnymi strukturami danych, aby uzyskać pożądany efekt. Odpowiedni wybó... Graf pełny: Taki graf, w którym każdy wierzchołek jest sąsiadem każdego innego. Powyższy graf nie jest pełny. Graf pełny o n wierzchołkach oznacza się przez Kn. Posiada on n * (n-1) / 2 krawędzi - tyle, ile par różnych wierzchołków. Klika: Podzbiór wierzchołków danego grafu, z których każdy jest sąsiadem każdego innego (czyli podgraf pełny). Graf ważony: Graf ważony to graf, w którym każdej krawędzi przypisana jest pewna waga. Wag używa się na przykład w algorytmie znajdowania optymalnej drogi. Graf planarny: Graf, który można narysować na płaszczyźnie w taki sposób, że żadne dwie krawędzie się nie przecinają. Powyższy graf jest planarny. Graf pełny Kn nie jest planarny dla n > 4. Graf eulerowski: Graf, który można narysować nie odrywając ołówka od papieru, przechodząc przy tym przez każdą krawędź dokładnie raz. Graf jest eulerowski wtedy i tylko wtedy gdy posiada dokładnie zero lub dwa wierzchołki o nieparzystej liczbie sąsiadów oraz musi być spójny. Graf hamiltonowski: Graf, który ma cykl przechodzący przez każdy wierzchołek dokładnie raz. Założeniem jest spójność grafu. Multigraf: Graf, w którym te same wierzchołki są połączone kilkoma krawędziami. Graf dwudzielny: Jeżeli w zbiorze wiechołków grafu można wydzielić dwa rozłączne podzbiory V1 i V2, tak, że każda krawędź grafu łączy wierzchołek ze zbioru V1 z wierzchołkiem ze zbioru V2, to taki graf jest grafem dwudzielnym. Zagadnienia teorii grafów
Zobacz też: przegląd zagadnień z zakresu matematyki programowanie sieciowe... Kategorie stron: Teoria grafów | Ekonomia matematyczna... | ||
![A=\left[ \begin{matrix} 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{matrix}\right]](/math.php?math=9a41d53d4469034adf9e19d38a316a0f.png)
|
Cache: OK - (Cache Hit) | Exec Czas: 0.141 | INTLinks: 37 Contakt: info AT definicja DOT com "teoria wyboru konsumenta" ""teoria pola" ekonomia matematyczna -elektromagnetycznego -klasyczna" "liczby ramseya" "kolorowanie wierzchołków grafu " ""problem najkrótszej ścieżki" " "kolorowanie grafów definicja" "algorytm zachłanny kolorowanie grafu" "problem najkrótszej ścieżki pomiędzy wszystkimi parami wierzchołków" "algorytm najbliższego sąsiada" "algorytm zachłanny komiwojażera" |