Opracował: Lesław Dereń
Zakład Teorii Obwodów
Instytut Telekomunikacji, Teleinformatyki i Akustyki
Politechnika Wrocławska
Prawa autorskie zastrze\
one
Termin 1
Podstawowe pojęcia z teorii grafów
Teoria grafów stanowi część działu matematyki, nazywanego topologią. W topologii
grafu nie definiuje się  jest on pojęciem podstawowym. Najczęściej graf jest uto\
samiany
z jego reprezentacją graficzną. Przykłady takich reprezentacji grafów przedstawiono na rys. 1.
wierzchołek
wierzchołek
krawędz

(a) (b) (c)
Rys. 1. Przykłady grafów
Reprezentacją grafu jest więc pewien zbiór punktów, nazywanych wierzchołkami grafu,
i zbiór połączeń między niektórymi z nich. Połączenia przedstawia się jako linie łączące
odpowiednie pary wierzchołków i nazywa się je krawędziami grafu. Nale\
y tu wyraz
nie
podkreślić, \
e nie mają znaczenia rozmiary, kształt czy sposób uło\
enia wierzchołków
i krawędzi na płaszczyz
nie (lub ogólniej  na dowolnej powierzchni lub w przestrzeni).
Istotne jest jedynie zachowanie struktury połączeń. Graf mo\
na więc sobie wyobrazić jako
pewną konstrukcję wykonaną z kawałków cienkiej gumy posklejanej w punktach
odpowiadającym wierzchołkom. Konstrukcję taką mo\
na w ró\
noraki sposób przekształcać
(rozciągać, skręcać czy rozmieszczać w przestrzeni) i, je\
eli w trakcie tych operacji niczego
nie porozrywamy ani nie posklejamy, to będziemy mieli do czynienia z tym samym grafem.
Dwie reprezentacje tego samego grafu przedstawiono na rys. 2.*
2
b
1
d
1
d
b
c
c
a
h
3
a
e
f
3 2
e
4
h
g
g
4 5 5
f
Rys. 2. Ró\
ne reprezentacje tego samego grafu
Czy z podobnymi właściwościami mo\
emy się spotkać w przypadku innych ni\
grafy
obiektów? Rozwa\
my obwód elektryczny, zbudowany z ró\
nych elementów połączonych
odcinkami przewodów. Własności elektryczne takiego obwodu nie będą zale\
ały ani od
*
Opisane przekształcenia są przykładem przekształceń homeomorficznych. Bardziej precyzyjnie
nale\
ałoby więc powiedzieć, \
e grafy z rys. 2 są grafami homeomorficznymi, czyli topologicznie równo-
wa\
nymi (nierozró\
nialnymi).
 ĆWICZENIA Z TECHNIKI ANALOGOWEJ 1  TERMIN 1 2
rozmieszczenia elementów, ani te\
od uło\
enia i długości połączeń. Oświetlenie choinkowe
nie zmieni swoich własności elektrycznych gdy choinka się przewróci. Podobieństwo do
własności grafów jest uderzające i sugeruje, \
e pewne własności obwodów (sieci)
elektrycznych będą identyczne z własnościami grafów.
Rozwa\
my obwód elektryczny N, przedstawiony na rys. 3a. Zbudowany jest on
z ró\
nego rodzaju elementów (nie wiemy jeszcze co to są za elementy, ale nie wpadajmy
w panikÄ™  na razie nie ma to \
adnego znaczenia), które będziemy nazywać gałęziami
obwodu. Elementy te są ze sobą połączone w sposób pokazany na schemacie. Punkty tych
połączeń stanowią węzły obwodu. Skonstruujmy teraz graf GN według następujących reguł:
- ka\
demu węzłowi obwodu N przyporządkujmy wierzchołek grafu GN,
- ka\
dej gałęzi obwodu N, łączącej węzły k i l, przyporządkujmy krawędz
grafu GN,
włączoną między wierzchołki k i l tego grafu.
Skonstruowany w ten sposób graf GN, przedstawiony na rys. 3b, nazywać będziemy
grafem sieciowym skojarzonym z obwodem N.
Cf
Re
4
4
e f
Rb
Lc
2
2 b c
1 3
1 3
d
ea
Cd Rg
a
g
5
5
(a) (b)
Rys. 3. Obwód elektryczny N  (a) i skojarzony z nim graf sieciowy GN  (b)
Obwód N i graf GN są obiektami topologicznie równowa\
nymi, mimo \
e fizycznie sÄ…
obiektami zupełnie ró\
nymi. W dalszych rozwa\
aniach zamiast  graf sieciowy skojarzony
z obwodem N  będziemy stosować uproszczone określenie  graf obwodu N  , a dla
podkreślenia, \
e chodzi o graf sieciowy będziemy uto\
samiać wierzchołki z węzłami
i krawędzie z gałęziami, czyli będziemy u\
ywać pojęć węzeł grafu i gałąz
grafu.
Obecnie wprowadzimy szereg określeń i definicji, stosowanych w teorii grafów. Ich
znajomość umo\
liwi w sposób prosty i jednoznaczny mówić o pewnych cechach,
własnościach i elementach obwodów elektrycznych, co będzie u\
yteczne w trakcie całego
kursu. Będziemy u\
ywać następujących pojęć:
- gałąz
jest incydentna z węzłem  węzeł jest jednym z końców tej gałęzi,
- stopień węzła  liczba gałęzi incydentnych z tym węzłem.
Definicja 1.
Podgrafem grafu G nazywa się graf G1, zawierający dowolny podzbiór właściwy zbioru
gałęzi grafu G. Dopełnieniem podgrafu G1 nazywamy graf G1 , zawierający te gałęzie grafu G,
które nie są gałęziami G1.
Definicja 2.
Ciągiem gałęzi nazywa się podgraf, którego gałęzie mo\
na uporządkować w taki sposób,
\
e koniec poprzedniej jest początkiem następnej. Ciągiem gałęzi mo\
e być równie\

pojedyncza gałąz
.
 ĆWICZENIA Z TECHNIKI ANALOGOWEJ 1  TERMIN 1 3
Definicja 3.
Przejściem nazywa się taki ciąg gałęzi, w którym węzeł początkowy i końcowy są
stopnia 1, natomiast pozostałe węzły (węzły wewnętrzne) są stopnia 2. Zbiór węzłów
wewnętrznych mo\
e być zbiorem pustym (czyli pojedyncza gałąz
jest przejściem).
Powy\
sze definicje zostały zilustrowane na rys. 4. Powinny być one intuicyjnie
zrozumiałe.
G1
G G1
f f
2 2
d e d e 2
1 3 1 3 3
1
a c c a
b b
g g
h h
4 6 4 6 4 6
5 5 5
i
i
(a) (b)
{a,g,b,d,f,c} {i,c,f,d} {f,a,g,b} {c,e}
f f
f
2 2
d d 2 2 3
e
1 3 1 3
1 3
a c c
b a c
b
g
g
4 6 4 6
4 6
5
5
i
(c) (d)
Rys. 4. Przykłady:
(a)  graf G
(b)  podgraf G1 grafu G i jego dopełnienie G1
(c)  ciągi gałęzi grafu G
(d)  przejścia w grafie G
Definicja 4.
Grafem spójnym nazywa się graf, w którym między dowolnymi dwoma węzłami istnieje
co najmniej jedno przejście.
Spośród grafów przedstawionych na rys. 1  4, nie są spójne grafy z rys. 1b i graf G1
z rys. 4b. Pozostałe grafy są spójne.
Definicja 5.
Grafem mocno spójnym nazywa się taki graf, którego dowolny podgraf ma co najmniej
dwa wspólne węzły ze swoim dopełnieniem.
Graf mocno spójny musi być oczywiście grafem spójnym i, dodatkowo, nie mo\
e mieć
tzw.  węzłów przegubowych . Zilustrowano to przykładami na rys. 5.
 ĆWICZENIA Z TECHNIKI ANALOGOWEJ 1  TERMIN 1 4
węzły przegubowe
(a) (b) (c)
Rys. 5. (a) i (b)  grafy spójne, mające węzły przegubowe , (c)  graf mocno spójny
Definicja 6.
Grafem planarnym nazywa się graf, który da się poło\
yć na płaszczyz
nie, tzn. mo\
na go
narysować na płaszczyz
nie w taki sposób, aby gałęzie nie przecinały się w punktach, które
nie są węzłami.
Zwracamy uwagÄ™, \
e nie chodzi tu o to jak graf jest narysowany, tylko czy da siÄ™
narysować w sposób spełniający warunki definicji. Graf z rys. 1c jest grafem planarnym 
wystarczy  przeło\
yć na zewnątrz jedną z wewnętrznych gałęzi. Przykłady grafów
nieplanarnych przedstawiono na rys. 6.*
Rys. 6, Przykłady grafów nieplanarnych
Definicja 7.
Oczkiem w grafie G nazywa się taki jego spójny podgraf L, w którym wszystkie węzły są
stopnia 2. Pojęcie to, chyba dosyć oczywiste, zostało zilustrowane przykładami przedstawio-
nymi na rys. 7.
L2
L1
f 2
d e
G
1 3
2
d e
1 3
f
a c
2
d e
1 3
4 6
L3 f
a c
b
i
L4
g 2 2
h e d e
1 3 1 3
4 6
5
a a c
b
i
g
g
h
4 5 4 6
5
Rys. 7. Graf G i przykłady oczek w tym grafie
Je\
eli w grafie sieci elektrycznej gałęzie tworzą oczko, to odpowiadające im gałęzie
w sieci tworzą obwód zamknięty. Taki obwód zamknięty, zgodnie z przyjętą konwencją
uto\
samiania pojęć, będziemy nazywać oczkiem w sieci elektrycznej.
*
Grafy te są w topologii nazywane grafami Kuratowskiego, który pierwszy udowodnił, \
e graf jest
nieplanarny wtedy i tylko wtedy gdy zawiera jako podgraf przynajmniej jeden z tych grafów.
 ĆWICZENIA Z TECHNIKI ANALOGOWEJ 1  TERMIN 1 5
Do dalszych rozwa\
ań wprowadzimy następujące oznaczenia:
- w  liczba węzłów grafu,
- g  liczba gałęzi grafu,
- p  liczba spójnych, wzajemnie rozłącznych części, z których składa się graf.
Liczby Á = w  p i µ = g  w + p bÄ™dziemy nazywać odpowiednio rzÄ™dem grafu
i liczbÄ… cyklomatycznÄ… grafu.
W zastosowaniu do analizy obwodów elektrycznych największe znaczenie mają grafy
spójne (dlaczego?). Je\
eli graf jest spójny, to oczywiście p = 1. Wówczas
Á = w  1,
µ = g  w + 1.
Definicja 8.
Przekrojem w grafie G nazywa się taki podzbiór S gałęzi grafu G, który ma następujące
własności:
a) usunięcie z grafu G wszystkich gałęzi tworzących zbiór S redukuje rząd grafu o 1,
b) \
aden podzbiór właściwy zbioru S nie ma własności a).
Mówiąc mniej precyzyjnie, przekrojem w grafie spójnym jest ka\
dy minimalny zbiór
gałęzi, których usunięcie z grafu (bez usuwania węzłów z którymi są incydentne) spowoduje
 rozpadnięcie się tego grafu na dwa spójne, wzajemnie rozłączne podgrafy (izolowany węzeł
traktujemy tu jako podgraf). Konstruowanie przekrojów jest bardzo proste w przypadku grafu
planarnego  wystarczy narysować linię (zamkniętą lub nie) rozcinającą graf, taką która nie
przechodzi przez \
aden z węzłów. Wówczas zbiór gałęzi, które ta linia przecina, tworzy
przekrój grafu. Zilustrowano to na rys. 8.
f
S1
2
d e
1 3
S1 = {i,g,b,e,f}
S2
S2 = {a,b,c}
a c
b S3 = {i,h,c}
S4 h S3
g
S4 = {g,b,h}
4 6
5
i
Rys. 8. Przykłady przekrojów w grafie
Zwracamy uwagÄ™, \
e np. zbiór gałęzi {g,b,e,h} nie jest przekrojem. Usunięcie tych gałęzi
z grafu redukuje wprawdzie jego rząd, ale istnieje podzbiór {g,b,h} tego zbioru, który
równie\
ma tę własność.
Szczególnym przykładem przekrojów są przekroje S3 i S4 w grafie z rys. 8. Przekroje te
są zbiorami gałęzi incydentnych odpowiednio z węzłami 6 i 5. Ogólnie, mo\
na stwierdzić, \
e
je\
eli węzeł nie jest węzłem przegubowym, to zbiór gałęzi incydentnych z tym węzłem jest
przekrojem.
Je\
eli w grafie skojarzonym z siecią elektryczną pewien zbiór gałęzi tworzy przekrój, to
zbiór odpowiadających im gałęzi sieci nazywać będziemy przekrojem sieci elektrycznej.
Pojęcia oczka i przekroju są wa\
nymi pojęciami w analizie obwodów elektrycznych.
Zgodnie z podstawowymi postulatami elektrotechniki, nazywanymi prawami Kirchhoffa,
algebraiczna suma prądów w gałęziach tworzących przekrój powinna być to\
samościowo
równa zero (I prawo Kirchhoffa) i, podobnie, algebraiczna* suma napięć na gałęziach
tworzących oczko powinna być to\
samościowo równa zero (II prawo Kirchhoffa). Na
*
U\
yte tu określenie  algebraiczna suma oznacza, \
e nale\
y uwzględnić kierunki prądów i napięć.
Zagadnieniem tym zajmiemy się w przyszłości, obecnie nie ma to znaczenia.
 ĆWICZENIA Z TECHNIKI ANALOGOWEJ 1  TERMIN 1 6
podstawie I prawa Kirchhoffa mo\
na więc uło\
yć tyle równań, ile jest wszystkich przekrojów,
a na podstawie II prawa Kirchhoffa  tyle równań, ile jest wszystkich oczek. Liczby tych
równań mogą być bardzo du\
e, rzędu kilkudziesięciu tysięcy, a nawet więcej. Z punktu
widzenia analizy interesujące są tylko te równania, które są liniowo niezale\
ne, a tych jest
zdecydowanie mniej. Mo\
na udowodnić następujące twierdzenia:
1. Liczba równań liniowo niezale\
nych, wynikających z I prawa Kirchhoffa, jest równa
rzÄ™dowi grafu sieci Á.
2. Liczba równań liniowo niezale\
nych, wynikających z II prawa Kirchhoffa, jest równa
liczbie cyklomatycznej grafu sieci µ.
Definicja 9.
Zbiór µ oczek nazywamy zbiorem oczek liniowo niezale\
nych, je\
eli układ równań
wynikajÄ…cych z II prawa Kirchhoffa, wypisanych dla tych oczek, jest liniowo niezale\
ny.
Definicja 10.
Zbiór Á przekrojów nazywamy zbiorem przekrojów liniowo niezale\
nych, je\
eli układ
równań wynikających z I prawa Kirchhoffa, wypisanych dla tych przekrojów, jest liniowo
niezale\
ny.
Przy analizie obwodu rzeczą istotną będzie więc odpowiedni wybór oczek (przekrojów),
dla których będziemy wypisywać równania wynikające z praw Kirchhoffa. Nale\
y je
wybierać tak, aby tworzyły one zbiór oczek (przekrojów) liniowo niezale\
nych. Zanim
zapoznamy się z metodami wyboru zbiorów oczek i przekrojów liniowo niezale\
nych
wprowadzimy jeszcze jedno pojęcie, bardzo wa\
ne w teorii grafów.
Rozwa\
my graf spójny G, mający w węzłów i g gałęzi, i skonstruujmy taki jego
podgraf T, który:
1. ma w węzłów (czyli wszystkie węzły grafu G),
2. ma (w  1) gałęzi,
3. jest spójny,
4. nie ma oczek.
Podgraf T nazywać będziemy drzewem grafu G. Przykłady drzew grafu przedstawiono
na rys. 9.
f
T1 T2
2 2
d e e
1 3 1 3
G
f b c
g
h h
2
d e
1 3
4 6 4 6
5 5
i
a c
b
T3 f T4
g
h
4
6
2 2
e e
d
5 3 3
1 1
i
c a
b
g
h
4 6
4 6
5 5
i
Rys. 9. Graf G i przykłady jego drzew
Przedstawionych własności świadomie nie nazwaliśmy definicją drzewa, bo jest ich za
du\
o! Mo\
na pokazać, \
e ka\
da z wymienionych czterech własności jest konsekwencją trzech
pozostałych. Jako definicję drzewa mo\
na więc przyjąć dowolne trzy z nich.
 ĆWICZENIA Z TECHNIKI ANALOGOWEJ 1  TERMIN 1 7
Odnotujmy jeszcze jednÄ… wa\
ną własność drzewa: między dowolnymi dwoma węzłami
drzewa istnieje dokładnie jedno przejście.
Gałąz
grafu G, która nie jest gałęzią drzewa T, nazywać będziemy łącznikiem tego
drzewa. Zbiór wszystkich łączników, liczący g  w + 1 gałęzi, stanowi dopełnienie T
drzewa T.
Je\
eli w grafie G wybierzemy drzewo T, a następnie dołączymy do tego drzewa jeden
z jego łączników, wówczas w nowym grafie (który oczywiście ju\
nie jest drzewem) pojawi
się dokładnie jedno oczko, zło\
one z dołączonego łącznika i gałęzi drzewa stanowiących
przejście (jedyne) między węzłami, do których został dołączony łącznik. Procedurę tę
mo\
emy kontynuować, dołączając kolejne łączniki. Za ka\
dym razem pojawia siÄ™ kolejne
jedno oczko (interesują nas tylko oczka, zło\
one z dołączonego właśnie łącznika i przejścia
po z gałęziach drzewa, a nie po dołączonych wcześniej łącznikach). Po wyczerpaniu całego
zbioru g  w + 1 = µ Å‚Ä…czników, wygenerowany zostanie zbiór µ oczek. Zbiór ten nazywać
będziemy fundamentalnym zbiorem oczek względem drzewa T.
Procedura konstruowania fundamentalnego zbioru oczek została zilustrowana na rys. 10.
Na rys. 10a przedstawiono graf G, na rys. 10b jego drzewo T (zaznaczone liniami ciągłymi),
dołączony łącznik b (zaznaczony linią przerywaną) i wygenerowane przez niego oczko,
natomiast na rys. 10c  fundamentalny zbiór oczek (względem drzewa T ).
f
f
2
2
d e d
1 3
1 3
a
a c b
b
g
h
4 6
4 6
g
5
5
i
i
(a) (b)
(c)
Rys. 10. Ilustracja konstruowania fundamentalnego zbioru oczek
Ze sposobu konstruowania fundamentalnego zbioru oczek wynika następująca własność:
ka\
dy łącznik drzewa T, względem którego utworzony został fundamentalny zbiór oczek,
nale\
y dokładnie do jednego oczka.
Mo\
na udowodnić następujące twierdzenie:
Zbiór oczek grafu G, fundamentalny względem dowolnego drzewa T tego grafu,
jest zbiorem oczek liniowo niezale\
nych, w sensie definicji 9.
Rozwa\
my obecnie graf G, w którym wybrane zostało drzewo T. Skonstruujmy teraz
zbiór w  1 = Á przekrojów tego grafu w taki sposób, aby ka\
da z gałęzi drzewa nale\
ała
dokładnie do jednego przekroju, tak jak to pokazano na rys. 11. Utworzony w ten sposób
zbiór Á przekrojów nazywać bÄ™dziemy fundamentalnym zbiorem przekrojów wzglÄ™dem
drzewa T.
Dowodzi się następującego twierdzenia:
Zbiór przekrojów grafu G, fundamentalny względem dowolnego drzewa T tego
grafu, jest zbiorem przekrojów liniowo niezale\
nych, w sensie definicji 10.
 ĆWICZENIA Z TECHNIKI ANALOGOWEJ 1  TERMIN 1 8
T = {b,d,e,h,i}
f
Fundamentalny zbiór przekrojów:
2
d e
1 3
Sb = {b,a,c}
Sd = {d,a,f}
a c
b
Se = {e,c,f}
g
h
Sh = {h,a,c,g}
4 6
5
Si = {i,a,g}
i
Rys. 11. Ilustracja konstruowania fundamentalnego zbioru przekrojów
W niektórych sytuacjach zbiory oczek i przekrojów niezale\
nych mo\
na wybrać
w prostszy sposób.
Je\
eli graf jest grafem planarnym i zostanie narysowany tak, aby gałęzie nie przecinały
się, to zbiór  klatek , na które została podzielona płaszczyzna, stanowi zbiór oczek liniowo
niezale\
nych.
Rozwa\
my graf mocno spójny. Nie zawiera on węzłów przegubowych, a więc zbiór
gałęzi incydentnych z ka\
dym z w węzłów tego grafu jest przekrojem. Mo\
na więc utworzyć
w przekrojów, z których ka\
dy będzie się składał ze zbioru gałęzi incydentnych
z odpowiednim węzłem. Dowodzi się, \
e dowolny zbiór, liczÄ…cy w  1 = Á tak utworzonych
przekrojów, stanowi zbiór przekrojów liniowo niezale\
nych.
Przedstawione metody zostały zilustrowane na rys. 12.
(a) (b)
Rys. 12. Ilustracja sposobu wyboru zbioru oczek (a) i przekrojów (b) liniowo niezale\
nych
Powy\
sze metody wyboru zbiorów oczek i przekrojów liniowo niezale\
nych są często
i chętnie stosowane, nale\
y jednak pamiętać, \
e wybór taki nie zawsze jest wyborem
optymalnym, w tym sensie, \
e nie zawsze prowadzi do równań o najprostszej postaci.
Zadania
Zad. 1.
W grafie z rys. 4a wskazać po trzy przykłady podgrafów, ciągów gałęzi i przejść
(ró\
nych od pokazanych w częściach (b), (c), (d) tego rysunku). Wskazać równie\

przykładowe oczka i przekroje w tym grafie.
Zad. 2.
Dany jest graf przedstawiony na rys. Z2. W grafie tym wybrano drzewo T = {a,b,c,d}.
Wskazać fundamentalne zbiory oczek i przekrojów względem tego drzewa. Powtórzyć to
zadanie przy innym wyborze drzewa.
 ĆWICZENIA Z TECHNIKI ANALOGOWEJ 1  TERMIN 1 9
1 2
b
g
f
c
a h i
5
d
e
j
3 4
Rys. Z2.
Zad. 3.
W grafie przedstawionym na rys. Z3 wybrano zaznaczony zbiór oczek liniowo
niezale\
nych. Czy istnieje drzewo T tego grafu, względem którego ten zbiór oczek będzie
zbiorem fundamentalnym? Odpowiedz
uzasadnić. Wybrać w grafie dowolne drzewo
i wskazać fundamentalne zbiory oczek i przekrojów względem tego drzewa.
b
1 2
e f
5 6
j
a c
i k
l
7 8
g
h
3 4
d
Rys. Z3.