Graf nieskierowany
DEFINICJA
Grafem nieskierowanym nazywamy parę G = (V , E ), gdzie V
jest pewnym zbiorem skończonym (zwanym zbiorem wierzchołków
grafu G ), natomiast E jest zbiorem nieuporządkowanych par
{v , u}, gdzie u, v ∈ V i u 6= v . Zbiór E nazywamy zbiorem
krawędzi grafu G .
Graf nieskierowany
PRZYKAD
(GRAF I) Zilustrować graf G = (V , E ), gdzie
V = {1, 2, 3, 4, 5, 6, 7} oraz
E = {{1, 2} , {1, 5}, {2, 5}, {3, 6}, {6, 7}}.
PRZYKAD
(GRAF II) Podać zbiory E i V poniższego grafu:
1
2
3
|
|
4
5
6
Graf nieskierowany
PRZYKAD
(GRAF I) Zilustrować graf G = (V , E ), gdzie
V = {1, 2, 3, 4, 5, 6, 7} oraz
E = {{1, 2} , {1, 5}, {2, 5}, {3, 6}, {6, 7}}.
PRZYKAD
(GRAF II) Podać zbiory E i V poniższego grafu:
1
2
3
|
|
4
5
6
Graf nieskierowany
PRZYKAD
(GRAF I) Zilustrować graf G = (V , E ), gdzie
V = {1, 2, 3, 4, 5, 6, 7} oraz
E = {{1, 2} , {1, 5}, {2, 5}, {3, 6}, {6, 7}}.
PRZYKAD
(GRAF II) Podać zbiory E i V poniższego grafu:
1
2
3
|
|
4
5
6
Graf nieskierowany
DEFINICJA
Jeżeli {u, v } jest krawędzią grafu nieskierowanego G , to mówimy ,
że (u, v ) jest incydentna z wierzchołkami u i v .
DEFINICJA
Stopniem wierzchołka w grafie nieskierowanym nazywamy liczbę
incydentnych z nim krawędzi.
WICZENIE
Podać stopień wierzchołka u = 6 grafu nr I.
Graf nieskierowany
DEFINICJA
Jeżeli {u, v } jest krawędzią grafu nieskierowanego G , to mówimy ,
że (u, v ) jest incydentna z wierzchołkami u i v .
DEFINICJA
Stopniem wierzchołka w grafie nieskierowanym nazywamy liczbę
incydentnych z nim krawędzi.
WICZENIE
Podać stopień wierzchołka u = 6 grafu nr I.
Graf nieskierowany
DEFINICJA
Jeżeli {u, v } jest krawędzią grafu nieskierowanego G , to mówimy ,
że (u, v ) jest incydentna z wierzchołkami u i v .
DEFINICJA
Stopniem wierzchołka w grafie nieskierowanym nazywamy liczbę
incydentnych z nim krawędzi.
WICZENIE
Podać stopień wierzchołka u = 6 grafu nr I.
Graf skierowany
DEFINICJA
Grafem skierowanym nazywamy parę G = (V , E ), gdzie V jest
pewnym zbiorem skończonym (zwanym zbiorem wierzchołków
grafu G ), natomiast E - zbiór krawędzi grafu G - jest zbiorem
uporządkowanych par {v , u} oznaczanych (v , u), gdzie u, v ∈ V .
Graf skierowany
PRZYKAD
(GRAF III) Zilustrować graficznie graf G = (V , E ), gdzie
V = {1, 2, 3, 4, 5, 6} oraz
E = {(1, 2), (2, 2), (2, 4), (2, 5), (4, 1), (4, 5), (5, 4), (6, 3)}.
PRZYKAD
(GRAF IV) Podać zbiory E i V poniższego grafu:
a
b
←−
c
&
%
&
%.
d
e
Graf skierowany
PRZYKAD
(GRAF III) Zilustrować graficznie graf G = (V , E ), gdzie
V = {1, 2, 3, 4, 5, 6} oraz
E = {(1, 2), (2, 2), (2, 4), (2, 5), (4, 1), (4, 5), (5, 4), (6, 3)}.
PRZYKAD
(GRAF IV) Podać zbiory E i V poniższego grafu:
a
b
←−
c
&
%
&
%.
d
e
Graf skierowany
DEFINICJA
Stopniem wierzchołka w grafie skierowanym nazywamy sumę
liczby krawędzi wchodzących do wierzchołka i wychodzących z
tego wierzchołka.
PRZYKAD
Podać stopień wierzchołka u = 2 w grafie III.
Graf skierowany
DEFINICJA
Stopniem wierzchołka w grafie skierowanym nazywamy sumę
liczby krawędzi wchodzących do wierzchołka i wychodzących z
tego wierzchołka.
PRZYKAD
Podać stopień wierzchołka u = 2 w grafie III.
DEFINICJA
Ścieżką (drogą) długości k z wierzchołka u do v w grafie G
nazywamy ciąg wierzchołków < v
0
, v
1
, ..., v
k
> takich, że
u = v
0
, v = v
k
,i (v
i −1
, v
i
) ∈ E dla i = 1, ..., k. Ścieżkę nazywamy
prostą , gdy jej wszystkie wierzchołki są różne.
PRZYKAD
Podać przykłady dróg
1
z wierzchołka u = 2 do wierzchołka v = 1 w grafie I;
2
z wierzchołka u = 1 do wierzchołka v = 3 w grafie I;
3
z wierzchołka u = 1 do wierzchołka v = 4 w grafie III;
4
z wierzchołka u = 3 do wierzchołka v = 6 w grafie III.
DEFINICJA
Ścieżką (drogą) długości k z wierzchołka u do v w grafie G
nazywamy ciąg wierzchołków < v
0
, v
1
, ..., v
k
> takich, że
u = v
0
, v = v
k
,i (v
i −1
, v
i
) ∈ E dla i = 1, ..., k. Ścieżkę nazywamy
prostą , gdy jej wszystkie wierzchołki są różne.
PRZYKAD
Podać przykłady dróg
1
z wierzchołka u = 2 do wierzchołka v = 1 w grafie I;
2
z wierzchołka u = 1 do wierzchołka v = 3 w grafie I;
3
z wierzchołka u = 1 do wierzchołka v = 4 w grafie III;
4
z wierzchołka u = 3 do wierzchołka v = 6 w grafie III.
DEFINICJA
Ścieżką (drogą) długości k z wierzchołka u do v w grafie G
nazywamy ciąg wierzchołków < v
0
, v
1
, ..., v
k
> takich, że
u = v
0
, v = v
k
,i (v
i −1
, v
i
) ∈ E dla i = 1, ..., k. Ścieżkę nazywamy
prostą , gdy jej wszystkie wierzchołki są różne.
PRZYKAD
Podać przykłady dróg
1
z wierzchołka u = 2 do wierzchołka v = 1 w grafie I;
2
z wierzchołka u = 1 do wierzchołka v = 3 w grafie I;
3
z wierzchołka u = 1 do wierzchołka v = 4 w grafie III;
4
z wierzchołka u = 3 do wierzchołka v = 6 w grafie III.
DEFINICJA
Ścieżką (drogą) długości k z wierzchołka u do v w grafie G
nazywamy ciąg wierzchołków < v
0
, v
1
, ..., v
k
> takich, że
u = v
0
, v = v
k
,i (v
i −1
, v
i
) ∈ E dla i = 1, ..., k. Ścieżkę nazywamy
prostą , gdy jej wszystkie wierzchołki są różne.
PRZYKAD
Podać przykłady dróg
1
z wierzchołka u = 2 do wierzchołka v = 1 w grafie I;
2
z wierzchołka u = 1 do wierzchołka v = 3 w grafie I;
3
z wierzchołka u = 1 do wierzchołka v = 4 w grafie III;
4
z wierzchołka u = 3 do wierzchołka v = 6 w grafie III.
DEFINICJA
Ścieżką (drogą) długości k z wierzchołka u do v w grafie G
nazywamy ciąg wierzchołków < v
0
, v
1
, ..., v
k
> takich, że
u = v
0
, v = v
k
,i (v
i −1
, v
i
) ∈ E dla i = 1, ..., k. Ścieżkę nazywamy
prostą , gdy jej wszystkie wierzchołki są różne.
PRZYKAD
Podać przykłady dróg
1
z wierzchołka u = 2 do wierzchołka v = 1 w grafie I;
2
z wierzchołka u = 1 do wierzchołka v = 3 w grafie I;
3
z wierzchołka u = 1 do wierzchołka v = 4 w grafie III;
4
z wierzchołka u = 3 do wierzchołka v = 6 w grafie III.
DEFINICJA
Ścieżką (drogą) długości k z wierzchołka u do v w grafie G
nazywamy ciąg wierzchołków < v
0
, v
1
, ..., v
k
> takich, że
u = v
0
, v = v
k
,i (v
i −1
, v
i
) ∈ E dla i = 1, ..., k. Ścieżkę nazywamy
prostą , gdy jej wszystkie wierzchołki są różne.
PRZYKAD
Podać przykłady dróg
1
z wierzchołka u = 2 do wierzchołka v = 1 w grafie I;
2
z wierzchołka u = 1 do wierzchołka v = 3 w grafie I;
3
z wierzchołka u = 1 do wierzchołka v = 4 w grafie III;
4
z wierzchołka u = 3 do wierzchołka v = 6 w grafie III.
DEFINICJA
Mówimy, że v jest osiągalny z u, gdy istnieje ścieżka z u do v .
PRZYKAD
Rozważmy graf III. Stwierdzić czy
1
wierzchołek u = 5 jest osiągalny z wierzchołka v = 4;
2
wierzchołek u = 3 jest osiągalny z wierzchołka v = 1;
3
wierzchołek u = 2 jest osiągalny z wierzchołka v = 5.
DEFINICJA
Mówimy, że v jest osiągalny z u, gdy istnieje ścieżka z u do v .
PRZYKAD
Rozważmy graf III. Stwierdzić czy
1
wierzchołek u = 5 jest osiągalny z wierzchołka v = 4;
2
wierzchołek u = 3 jest osiągalny z wierzchołka v = 1;
3
wierzchołek u = 2 jest osiągalny z wierzchołka v = 5.
DEFINICJA
Mówimy, że v jest osiągalny z u, gdy istnieje ścieżka z u do v .
PRZYKAD
Rozważmy graf III. Stwierdzić czy
1
wierzchołek u = 5 jest osiągalny z wierzchołka v = 4;
2
wierzchołek u = 3 jest osiągalny z wierzchołka v = 1;
3
wierzchołek u = 2 jest osiągalny z wierzchołka v = 5.
DEFINICJA
Mówimy, że v jest osiągalny z u, gdy istnieje ścieżka z u do v .
PRZYKAD
Rozważmy graf III. Stwierdzić czy
1
wierzchołek u = 5 jest osiągalny z wierzchołka v = 4;
2
wierzchołek u = 3 jest osiągalny z wierzchołka v = 1;
3
wierzchołek u = 2 jest osiągalny z wierzchołka v = 5.
DEFINICJA
Mówimy, że v jest osiągalny z u, gdy istnieje ścieżka z u do v .
PRZYKAD
Rozważmy graf III. Stwierdzić czy
1
wierzchołek u = 5 jest osiągalny z wierzchołka v = 4;
2
wierzchołek u = 3 jest osiągalny z wierzchołka v = 1;
3
wierzchołek u = 2 jest osiągalny z wierzchołka v = 5.
Cykle
DEFINICJA
Mówimy, że w grafie skierowanym ścieżka < v
0
, v
1
, ..., v
k
>
tworzy cykl, jeśli v
0
= v
k
oraz zawiera ona co najmniej jedna
krawędź. Cykl nazywamy prostym, gdy v
1
, ..., v
k
są różne.
DEFINICJA
Pętlą nazywamy cykl o długosci 1.
Cykle
DEFINICJA
Mówimy, że w grafie skierowanym ścieżka < v
0
, v
1
, ..., v
k
>
tworzy cykl, jeśli v
0
= v
k
oraz zawiera ona co najmniej jedna
krawędź. Cykl nazywamy prostym, gdy v
1
, ..., v
k
są różne.
DEFINICJA
Pętlą nazywamy cykl o długosci 1.
Cykle
DEFINICJA
Mówimy, że ścieżka < v
0
, v
1
, ..., v
k
> tworzy cykl w grafie
nieskierownym, gdy v
0
= v
k
, v
1
, ..., v
k
są różne i k 2.
DEFINICJA
Graf nie zawierający cykli nazywamy acyklicznym.
Cykle
DEFINICJA
Mówimy, że ścieżka < v
0
, v
1
, ..., v
k
> tworzy cykl w grafie
nieskierownym, gdy v
0
= v
k
, v
1
, ..., v
k
są różne i k 2.
DEFINICJA
Graf nie zawierający cykli nazywamy acyklicznym.
PRZYKAD
Podać przykład
1
ścieżki prostej w grafie III;
2
ścieżki cyklu w grafie III;
3
ścieżki cyklu prostego w grafie III;
4
ścieżki prostej w grafie I;
5
ścieżki prostej w grafie II.
6
grafu zawierającego pętlę.
PRZYKAD
Podać przykład
1
ścieżki prostej w grafie III;
2
ścieżki cyklu w grafie III;
3
ścieżki cyklu prostego w grafie III;
4
ścieżki prostej w grafie I;
5
ścieżki prostej w grafie II.
6
grafu zawierającego pętlę.
Zagadnienia na egzamin
Zasada indukcji matematycznej.
Własności funkcji sufitu lub podłogi. Równania zawierające
funkcje sufitu lub podłogi (w zbiorze liczb rzeczywistych lub
naturalnych).
Notacje asymptotyczne ( szeregowanie rzędów wielkości).
Asymptotyczne oszacowań dla sum z wykorzystaniem
twierdzenia o szacowaniu sum za pomocą całek.
Oszacowania asymptotyczne rozwiązań rekurencji typu
T(n)=aT(n/b)+f(n) –twierdzenie o rekurencji uniwersalnej.
Funkcje tworzące (generowanie funkcji tworzącej zadanego
ciągu; wyznaczanie ciągu generującego zadaną funkcję
tworzącą) .
Zagadnienia na egzamin
Zasada indukcji matematycznej.
Własności funkcji sufitu lub podłogi. Równania zawierające
funkcje sufitu lub podłogi (w zbiorze liczb rzeczywistych lub
naturalnych).
Notacje asymptotyczne ( szeregowanie rzędów wielkości).
Asymptotyczne oszacowań dla sum z wykorzystaniem
twierdzenia o szacowaniu sum za pomocą całek.
Oszacowania asymptotyczne rozwiązań rekurencji typu
T(n)=aT(n/b)+f(n) –twierdzenie o rekurencji uniwersalnej.
Funkcje tworzące (generowanie funkcji tworzącej zadanego
ciągu; wyznaczanie ciągu generującego zadaną funkcję
tworzącą) .
Zagadnienia na egzamin
Zasada indukcji matematycznej.
Własności funkcji sufitu lub podłogi. Równania zawierające
funkcje sufitu lub podłogi (w zbiorze liczb rzeczywistych lub
naturalnych).
Notacje asymptotyczne ( szeregowanie rzędów wielkości).
Asymptotyczne oszacowań dla sum z wykorzystaniem
twierdzenia o szacowaniu sum za pomocą całek.
Oszacowania asymptotyczne rozwiązań rekurencji typu
T(n)=aT(n/b)+f(n) –twierdzenie o rekurencji uniwersalnej.
Funkcje tworzące (generowanie funkcji tworzącej zadanego
ciągu; wyznaczanie ciągu generującego zadaną funkcję
tworzącą) .
Zagadnienia na egzamin
Zasada indukcji matematycznej.
Własności funkcji sufitu lub podłogi. Równania zawierające
funkcje sufitu lub podłogi (w zbiorze liczb rzeczywistych lub
naturalnych).
Notacje asymptotyczne ( szeregowanie rzędów wielkości).
Asymptotyczne oszacowań dla sum z wykorzystaniem
twierdzenia o szacowaniu sum za pomocą całek.
Oszacowania asymptotyczne rozwiązań rekurencji typu
T(n)=aT(n/b)+f(n) –twierdzenie o rekurencji uniwersalnej.
Funkcje tworzące (generowanie funkcji tworzącej zadanego
ciągu; wyznaczanie ciągu generującego zadaną funkcję
tworzącą) .
Zagadnienia na egzamin
Zasada indukcji matematycznej.
Własności funkcji sufitu lub podłogi. Równania zawierające
funkcje sufitu lub podłogi (w zbiorze liczb rzeczywistych lub
naturalnych).
Notacje asymptotyczne ( szeregowanie rzędów wielkości).
Asymptotyczne oszacowań dla sum z wykorzystaniem
twierdzenia o szacowaniu sum za pomocą całek.
Oszacowania asymptotyczne rozwiązań rekurencji typu
T(n)=aT(n/b)+f(n) –twierdzenie o rekurencji uniwersalnej.
Funkcje tworzące (generowanie funkcji tworzącej zadanego
ciągu; wyznaczanie ciągu generującego zadaną funkcję
tworzącą) .
Zagadnienia na egzamin
Zasada indukcji matematycznej.
Własności funkcji sufitu lub podłogi. Równania zawierające
funkcje sufitu lub podłogi (w zbiorze liczb rzeczywistych lub
naturalnych).
Notacje asymptotyczne ( szeregowanie rzędów wielkości).
Asymptotyczne oszacowań dla sum z wykorzystaniem
twierdzenia o szacowaniu sum za pomocą całek.
Oszacowania asymptotyczne rozwiązań rekurencji typu
T(n)=aT(n/b)+f(n) –twierdzenie o rekurencji uniwersalnej.
Funkcje tworzące (generowanie funkcji tworzącej zadanego
ciągu; wyznaczanie ciągu generującego zadaną funkcję
tworzącą) .
Zagadnienia na egzamin
Zasada indukcji matematycznej.
Własności funkcji sufitu lub podłogi. Równania zawierające
funkcje sufitu lub podłogi (w zbiorze liczb rzeczywistych lub
naturalnych).
Notacje asymptotyczne ( szeregowanie rzędów wielkości).
Asymptotyczne oszacowań dla sum z wykorzystaniem
twierdzenia o szacowaniu sum za pomocą całek.
Oszacowania asymptotyczne rozwiązań rekurencji typu
T(n)=aT(n/b)+f(n) –twierdzenie o rekurencji uniwersalnej.
Funkcje tworzące (generowanie funkcji tworzącej zadanego
ciągu; wyznaczanie ciągu generującego zadaną funkcję
tworzącą) .
Zagadnienia na egzamin
Zliczanie (prawa sumy, iloczynu i potęgi, wariacje, permutacje,
kombinacje, zasada szufladkowa Dirichleta)
Równania różnicowe (operator różnicy i jego własności,
własności operatora E, wykorzystanie obu operatorów do
wyznaczania sum skończonych, twierdzenie Montmorta o
sumowaniu nieskończonym, równania różnicowe liniowe rzędu
r ze stałymi współczynnikami).
Grafy – podstawowe definicje.
Zagadnienia na egzamin
Zliczanie (prawa sumy, iloczynu i potęgi, wariacje, permutacje,
kombinacje, zasada szufladkowa Dirichleta)
Równania różnicowe (operator różnicy i jego własności,
własności operatora E, wykorzystanie obu operatorów do
wyznaczania sum skończonych, twierdzenie Montmorta o
sumowaniu nieskończonym, równania różnicowe liniowe rzędu
r ze stałymi współczynnikami).
Grafy – podstawowe definicje.
Zagadnienia na egzamin
Zliczanie (prawa sumy, iloczynu i potęgi, wariacje, permutacje,
kombinacje, zasada szufladkowa Dirichleta)
Równania różnicowe (operator różnicy i jego własności,
własności operatora E, wykorzystanie obu operatorów do
wyznaczania sum skończonych, twierdzenie Montmorta o
sumowaniu nieskończonym, równania różnicowe liniowe rzędu
r ze stałymi współczynnikami).
Grafy – podstawowe definicje.
Zagadnienia na egzamin
Zliczanie (prawa sumy, iloczynu i potęgi, wariacje, permutacje,
kombinacje, zasada szufladkowa Dirichleta)
Równania różnicowe (operator różnicy i jego własności,
własności operatora E, wykorzystanie obu operatorów do
wyznaczania sum skończonych, twierdzenie Montmorta o
sumowaniu nieskończonym, równania różnicowe liniowe rzędu
r ze stałymi współczynnikami).
Grafy – podstawowe definicje.
Wyszukiwarka
Podobne podstrony:
Wykład 2 Materiały pomocnicze (2012)
Materiały pomocne przy nauce podsumowanie powyższych wykładów wersja mini
Gibas M Chemia makroczasteczek Materiały pomocnicze do wykładu
Materiały pomocnicze do wykładów, FiR, Notatki, Rynki finansowe
materiały pomocnicze do wykładu nr 5
materialy pomocnicze do wykladow z genoterapii, Biotechnologia CM UMK USM, Semestr II, Genoterapia (
Gospodarka przestrzenna - materiały pomocnicze do wykładów, Polibuda, Gospodarka przestrzenna
material pomocniczy do zaliczenia ustnego ćwiczen, wsr rok 1 2012, wykłady, I semestr, fizjo
Maszyny i Urządzenia Technologiczne txI-2, Materiały pomocnicze studenta, Wykłady, Maszyny i Urządze
materiały pomocnicze do wykładu nr 4
materiały pomocnicze do wykładu nr 3
materiały pomocnicze do wykładu nr 2
Ekologia materialy pomocnicze do wykladow
Materiały pomocne przy nauce podsumowanie powyższych wykładów wersja mini
więcej podobnych podstron