Grafy -- teoria

10.11.2009
Trudność

Graf, to pojęcie, które jest fundamentalne dla zrozumienia większości olimpijskich problemów i ich rozwiązań. Definicję na pewno znajdziecie w sieci, a większość opracowań zadań używa go bez zbędnych wyjaśnień.

Formalnie, graf jest parą. Piszemy $ G=(V,E) $ mając na myśli, że graf $ G $ jest parą, której pierwszym elementem jest $ V $ a drugim $ E $. Graf jest parą, której pierwszym elementem jest zbiór wierzchołków, a drugim pewna relacja. Relacja to pojęcie fundamentalne dla logiki i wiele ciekawych matematycznych pojęć jak "porządek", czy "klasa abstrakcji", bazują na nim. Formalnie relacja k-argumentowa to pewien podzbiór zawarty w iloczynie kartezjańskim k zbiorów. Taka formalna definicja pewnie nieco odstrasza, a nam nie jest potrzebna w całym brzmieniu, bo interesować nas będą tylko relacje 2-argumentowe, czyli binarne, czyli "strzałki" prowadzące od jednego argumentu do drugiego. Zbiór krawędzi jest relacją dwuargumentową która zachodzi pomiędzy elementami $ V $.

Formalnie powiedzielibyśmy, że zbiór $ E $ zawiera się w $ V \times V $, czyli w iloczynie kartezjańskim zbioru $ V $ z nim samym. Krzyżyk oznacza iloczyn kartezjański. Definicję oczywiście znaleźć można w sieci, ale nam wystarczy do szczęścia rozumieć to poprzez następującą analogię do języka C++:  jeśli mamy jakieś dwa typy S oraz T, to

1
pair<T,S>
reprezentuje iloczyn kartezjański zbioru T i zbioru S, bowiem do zbioru elementów o typie pair<T,S> należą takie pary p, że p.first ma typ $ T $, zaś p.second ma typ $ S $.
Mniej formalnie mówimy, że $ E $ to taki zbiór strzałek pomiędzy elementami V.

Zbiór wierzchołków, może być dowolnym zbiorem, ale najczęściej interesują nas skończone zbiory. Elementy skończonego zbioru najwygodniej jest sobie ponumerować liczbami naturalnymi od 1 do n, gdzie $ n=|V| $ jest liczbą elementów zbioru V. Nawet jeśli w zadaniu pojawia się graf, którego elementy mają inne nazwy (np. miasta, których nazwy to jakieś słowa) to i tak lepiej jest myśleć o liczbach.

Podobnie krawędzie, choć często w zadaniu nazywają się "drogami", "korytarzami", "znajomościami", czy jeszcze inaczej, najprościej nazywać krawędziami i myśleć o nich jak o parach liczb.

Grafy dzielimy na skierowane i nieskierowane. Graf nieskierowany to taki, w którym każda krawędź $ (x,y) $ posiada swoją bliźniaczą krawędź $ (y,x) $. Formalnie mówimy, wtedy że relacja E jest symetryczna. Grafy nieskierowane często rysujemy przy pomocy kresek a nie strzałek, rozumiejąc, że taka kreska oznacza krawędź w obie strony. W zadaniach często pojawiają się "drogi jednokierunkowe" bądź "korytarze dwukierunkowe" i wtedy od razu wiemy, czy mowa jest o grafie skierowanym czy nieskierowanym.

Przykłady:

Graf skierowany, który wygląda jak trójkąt, możemy nazwać T i napisać $ T=(\{1,2,3\} ,\{(1,2),(2,3),(3,1)\} ) $, a więc $ V=\{1,2,3\} $, $ n=3 $, $ E=\{(1,2),(2,3),(3,1)\} $, $ m=3 $.

Jak widać, zbiory oznaczamy nawiasami wąsatymi: $ \{ \} $, zaś pary nawiasami okrągłymi $ ( ) $. Różnica między parą a zbiorem dwuelementowym jest taka, że w zbiorze kolejność elementów nie ma znaczenia a więc $ \{1,2\} = \{2,1\} $, podczas gdy w parach ma znaczenie: $ (1,2) $ to nie to samo co $ (2,1) $. Dlatego też o krawędziach nieskierowanych myśli się niekiedy jak o zbiorach dwuelementowych, podczas gdy o krawędziach skierowanych jak o parach.

Graf nieskierowany, który wygląda jak kwadrat, możemy nazwać K i napisać $ K=( \{a,b,c,d\}, \{ \{a,b\},\{b,c\},\{d,a\},\{d,c\} \} ) $.

5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com