Matematyka dyskretna 2002 - 09 Grafy nieskierowane, materiały naukowe do szkół i na studia, Matematyka chomikuj, ...

[ Pobierz całość w formacie PDF ]
Matematyka Dyskretna
Andrzej Szepietowski
25 czerwca 2002 roku
Rozdział 1
Grafy (nieskierowane)
Denicja 1.1
Graf (nieskierowany)
jest to para składaj aca sie ze sko n-
czonego zbioru wierzchołków
oraz ze zbioru krawedzi
, gdzie krawedzie to pary
wierzchołków.
O krawedzi
*
mówimy, ze łaczy wierzchołki
i
, a o wierzchołkach
i
,
ze sa ko ncami krawedzi
*
.
Stopie n wierzchołka
, oznaczany przez
/
, jest to liczba
.
Graf czesto przedstawiamy na rysunku jako zbiór punktów (lub kółek) połaczonych
odcinkami (lub łukami).
Rysunek 1.1: Przykład grafu
Przykład 1.2
Rysunek 1.1 przedstawia graf
ze zbiorem wierzchołków
i zbiorem krawedzi
3
.
krawedzi wychodzacych z
4
Rozdział 1. Grafy (nieskierowane)
Stopie n wierzchołk w
i
5
wynosi 4, wierzchołki
4
i
6
s a stopnia 3, wierzchołki
,
/
i
stopnia 2.
Lemat 1.3
Niech
, bedzie dowolnym grafem z
krawedziami. Wtedy
Dowód:
Jezeli policzymy wszystkie krawedzie wychodzace ze wszystkich wierzchołków
grafu, to z jednej strony mamy sume
/
, a z drugiej
poniewaz kazda
krawedz
*
jest liczona dwa razy, raz jak liczymy krawedzie wychodzace z
A
i
drugi raz jak liczymy krawedzie wychodzace z
.
Wniosek 1.4
Liczba wierzchołków o nieparzystych stopniach jest parzysta.
Graf
nazywamy
podgrafem
grafu
, jezeli
.
Przykład 1.5
Grafy przedstawione na rysunkach 1.5 i 1.6 s a podgrafami grafu z rysun-
ku 1.1 . Graf
.
z rysuku 1.5 zawiera szesc wierzchołków
i trzy krawedzie
.
;
<
Graf
;<
>
z rysuku 1.6 zawiera siedem wierzchołków
i piec krawedzi
.
Graf pełny
o
wierzchołkach, oznaczany przez
, jest to graf z
wierzchołkami,
>.
;
w którym kazde dwa wierzchołki połaczone sa krawedzia.
Rysunek 1.2: a) Graf pełny
. b) Graf pełny dwudzielny
a
b
a
b
c
d
c
d
e
f
e
f
a)
b)
Graf
jest
dwudzielny
, jezeli zbiór jego wierzchołków mozna rozbi c na
dwie czesci
,
, tak, ze kazda krawedz
*
ma ko nce w
obu zbiorach
i
:7
&
.
Pełny graf dwudzielny
$
ma zbiór wierzchołków rozbity na
:7
!
#"
dwa podzbiory:
i
, a krawedzie łacza kazdy
wierzchołek z
z kazdym wierzchołkiem z
, czyli
&%
7
(?(?(
’%
.
)(
*%,+
A
8
.-
/102/
-
/
oraz
1.1. Izomorzm grafów
5
1.1 Izomorzm grafów
Izomorzmem grafu
na graf
nazywamy funkcje wza-
jemnie jednoznaczna
spełniajaca warunek:
wtedy i tylko
wtedy, gdy
. Jezeli taka funkcja istnieje, to mówimy, ze grafy
i
sa izomorczne. Łatwo sprawdzic, ze izomorzm grafów jest relacja równowaznosci.
Przykład 1.6
Rysunki 1.3a i 1.3b przedstawiaj a ten sam graf
ze zbiorem
wierzchołków
oraz zbiorem krawedzi
).
Graf
z rysunku 1.4a jest izomorczny z grafem
. Izomorzmem z
na
jest funkcja
okreslona nastepuj aco:
,
,
,
>.
,
.
Graf
z rysunku 1.4b nie jest izomorczny z grafami
i
. Graf
zawiera
wierzchołek
/
stopnia jeden, a w grae
takiego wierzchołka nie ma.
Rysunek 1.3: Rysunki a) i b) przedstawiaja ten sam graf
a
b
a
d
c
d
b
c
a)
b)
Rysunek 1.4: a) Graf
izomorczny z
. b) Graf
nieizomorczny z
a
b
a
b
c
d
c
d
a)
b)
Jezeli mamy izomorzm grafu
na graf
, to mozemy
powiedziec, ze
jest takim samym grafem co
tylko ze zmienionymi nazwami wierz-
chołków.
Twierdzenie 1.7
Jezeli grafy
i
s a izomorczne, to:
=
.
[ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • mement.xlx.pl

    • Tematy