Wstęp do Teorii Grafów

10.12.2009 - Kacper Król
Trudność

W niniejszym artykule przedstawimy parę pojęć i zagadnień, dzięki którym będziemy mogli w konkretny sposób opisywać problemy, a także w łatwy sposób rozwiązywać je. Mowa tu o grafach. [Początki tej dziedziny sięgają XVIII wieku, kiedy to właśnie za pomocą tej struktury – grafu – udało się rozwiązać problem pewnego spaceru]. Zapraszam zatem do lektury!

Wiele rzeczy, które nas otacza lub zjawiska, które dają się zaobserwować, można opisać za pomocą relacji binarnej, tj. pewnej zależności występującej między dwoma obiektami. Przykładowo możemy powiedzieć, że Wrocław jest w relacji ‘istnieje droga’ z Poznaniem, ponieważ z Wrocławia da się dojechać do Poznania, ale już Wrocław i Sydney nie będą 
w takiej relacji (mowa tu o podróżowaniu samochodem, tudzież pieszo). Podobnie możemy opisać łańcuch pokarmowy, za pomocą relacji ‘jest zjadany przez’, np. mysz jest w takiej relacji z kotem, a kot z ...Alfem?

 
Musimy teraz sprecyzować parę pojęć, żebyśmy mieli pewność, że mówiąc o ‘drodze’ w grafie lub o ‘grafie prostym’ myślimy o tym samym :).

Zacznijmy od samego grafu $ G $: to para składająca się ze zbioru wierzchołków $ V $ i zbioru krawędzi $ E $. $ G = \left(V,E\right) $. Krawędzie możemy opisywać za pomocą par $ \left(v,w\right) $ lub $ 2 $ - elementowych zbiorów $ \left\{v,w\right\} $, gdzie $ v $ i $ w $ są wierzchołkami grafu. Co w skrócie będziemy zapisywać $ vw $.
W naszych przykładach, zbiorem wierzchołków mogłyby być miasta: {Wrocław, Poznań, Łódź, Katowice}, a w zbiorze krawędzi znalazłyby się pary miast, między którymi można podróżować: { {Wrocław, Poznań}, {Wrocław, Katowice}, {Łódź, Poznań}, ...}.

Intuicyjnie można wprowadzić pojęcie ‘sąsiedztwa’. Mówimy, że dwa wierzchołki są sąsiednie, jeśli istnieje między nimi krawędź: czyli Wrocław i Poznań są sąsiednie, a Poznań i Sydney nie (rys.1.).

Liczbę krawędzi wychodzących z wierzchołka $ v $ nazywamy stopniem wierzchołka i oznaczamy $ deg\left(v\right) $.


Żeby oswoić się z pojęciami, zastanówmy się nad następująca zagadką:


W międzyszkolnych rozgrywkach w hokeja (dla ułatwienia może to być piłka nożna) wzięło udział $ n $ drużyn. Każda z drużyn rozegrała odpowiednio $ d_{1}, d_{2}, ... d_{n} $ meczów (każdy mecz odbył się w innym terminie). Ile biletów było potrzebnych, żeby obejrzeć wszystkie mecze?

Spróbujmy utworzyć graf dla tych rozgrywek. Wierzchołkami w tym grafie będą drużyny. Krawędziami połączymy te z nich, które rozegrały między sobą mecz. Jeżeli zsumujemy liczbę spotkań, którą rozegrała każda drużyna, to na pewno żadnego nie przeoczymy, ale w ten sposób mecz $ A $ z $ B $ potraktujemy jako inny, niż $ B $ z $ A $. Mamy zatem:
  $ d_{1} + d_{2} + d_{3} + ... + d_{n} = 2M $, gdzie $ M $ to liczba meczów1.

Wiemy już zatem ile musielibyśmy kupić biletów, żeby dostać czapkę wiernego kibica :)

(1Jest to lemat o uściskach dłoni mówiący, że suma stopni wierzchołków w grafie jest równa podwojonej liczbie krawędzi tego grafu.)

4.333335
Twoja ocena: Brak Ocena: 4.3 (6 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com