W Y K Ł A D 15
15.1. Metody sieciowe analizy obwodów SLS
Rys. 15.1. Obwód elektryczny o liczbie gałęzi g = 6 i liczbie węzłów w = 4
· gałąź obwodu elektrycznego tworzy jeden lub kilka połączonych ze sobą szeregowo elementów idealnych; jej cechą charakterystyczną jest prąd,
· węzłem obwodu elektrycznego nazywa się końcówkę (zacisk) wyprowadzoną na zewnątrz, do której jest lub może być przyłączona następna gałąź lub kilka gałęzi; węzłowi odpowiada potencjał.
15.1.1. Elementy teorii grafów
Niech B oznacza zbiór elementów bl zwanych krawędziami (gałęziami), tzn. bl Î B oraz niech V oznacza zbiór elementów vk zwanych wierzchołkami (węzłami), tzn. vk Î V . Zakłada się, że zbiory B, V , są skończone i rozłączne[1] oraz że zbiór V nie jest pusty, tzn. V ¹ F .
Grafem G nazywa się odwzorowanie (incydencja[2]): . (15.33)
Jeżeli krawędzi (gałęzi) bl Î B jest w grafie przyporządkowana para wierzchołków (węzłów) (vi , vj ) Î , to zapisuje się to w postaci
(15.34)
Rys.15.2. Elementy grafu G : a) nieskierowana (niezorientowana) krawędź bl grafu G , b) skierowana (zorientowana) krawędź bl grafu G , c) pętla własna wierzchołka (węzła) vi , d) wierzchołek (węzeł) izolowany vi
, (15.36)
oraz
. (15.37)
Rys.15.3. Graf G o liczbie krawędzi (gałęzi) g = 6 i liczbie wierzchołków (węzłów) w = 4; a) graf nieskierowany (niezorientowany), b) graf skierowany (zorientowany), c) graf zorientowany równoważny grafowi z rys. 15.3b
Jeżeli oraz oraz graf , (15.38)
to jest podgrafem grafu G , tzn. . (15.38a)
Rys.15.4. Przykłady podgrafów grafu G ; a) podgraf , b) dopełnienie podgrafu
Rzędem (stopniem) wierzchołka (węzła) w grafie nazywa się liczbę krawędzi (gałęzi) incydentnych z tym wierzchołkiem (węzłem). Jeśli wierzchołek ma pętle własne, to rząd wierzchołka liczy się podwójnie. Ilustruje to rys.15.5.
Rys.15.5. Przykład grafu do wyznaczania rzędu węzłów; 1 - 0, 2 - 3, 3 - 4, 4 -1, 5 - 5, 6 - 3, 7 -4
Wierzchołek o rzędzie równym jeden nazywa się wierzchołkiem wiszącym zaś krawędź z nim incydentną nazywa się krawędzią wiszącą.
Drogą D w grafie G nazywa się skończony ciąg wierzchołków i krawędzi grafu o postaci:
, (15.39)
spełniający warunki:
· każda krawędź jest incydentna z występującym obok niej wierzchołkiem, tzn.
, (15.39a)
· wszystkie wierzchołki są różne.
Przykładem drogi w grafie z rys.15.3b jest .
Konturem lub cyklem K w grafie G (skierowanym lub nieskierowanym) nazywa się ciąg D w którym , tzn.
, (15.40)
Przykładem konturu dla grafu z rys.15.3 jest ciąg jak również tym samym konturem jest , co oznacza, że nie jest istotny wybór wierzchołka początkowego dla konturów zawierających dokładnie te same krawędzie z zachowaniem ich cyklicznej kolejności.
Zwrot konturu K jest wyznaczony przez cykliczną kolejność krawędzi występujących w ciągu (15.40).
Zapis drogi D lub konturu K można uprościć podając tylko ciąg oznaczeń krawędzi, np. , .
Oczkiem O nazywa się taki kontur, wewnątrz którego nie ma krawędzi grafu, zaś jego zwrot przyjmuje się jako zgodny z ruchem wskazówek zegara. Dla grafu z rys.15.3 oczkami są: , i .
Oczkiem odniesienia ON jest kontur, którego reprezentacja geometryczna jest brzegiem obszaru nieograniczonego nie zawierającego krawędzi („zewnętrznego” w stosunku do grafu). Zwrot oczka odniesienia jest przeciwny do ruchu wskazówek zegara. . Dla grafu z rys.15.3 oczkiem odniesienia jest .
Ścieżką S w grafie skierowanym G nazywa się drogę, której wszystkie krawędzie są skierowane z jej zwrotem. . Dla grafu z rys.15.3b ścieżkami są: , , , , , , . Nie jest ścieżką gdyż ciąg ten tworzy kontur (także oczko odniesienia).
Pętlą P w grafie skierowanym G nazywa się taki kontur, którego wszystkie krawędzie są skierowane zgodnie z jej zwrotem. Na rys.15.3b jedyną pętlą jest .
Graf G jest spójny, jeśli dla każdej pary wierzchołków vi , vj Î V oraz vi ¹ vj istnieje droga D w grafie G , do której wierzchołki te należą.
Graf G jest silnie spójny, jeśli dla każdej pary wierzchołków vi , vj Î V oraz vi ¹ vj istnieje kontur K w grafie G , do którego wierzchołki te należą. Graf z rys.15.4a jest spójny, ale nie mocno (silnie) spójny.
Graf G jest rozłączny, jeżeli między dowolnymi dwoma wierzchołkami nie ma drogi – rys.15.6.
Rys.15.6. Graf rozłączny
Graf posiada węzeł przegubowy wtedy, gdy po jego rozcięciu graf rozpada się na dwa grafy mocno spójne – rys.15.7.
Rys.15.7. Graf z węzłem przegubowym
Stąd też definiuje się graf mocno spójny jako graf, który nie ma węzła przegubowego.
15.1.2. Grafy sieciowe
Strukturę sieci przedstawia się za pomocą grafu sieciowego, który jest modelem geometrycznym układu gałęzi i węzłów sieci.
Każdej gałęzi grafu sieciowego przypisuje się zwrot zgodnie z przyjętym zwrotem prądu gałęziowego, otrzymując graf skierowany (zorientowany). Przy tworzeniu grafu idealne źródła napięcia traktuje się jako zwarcie, a idealne źródła prądu jako przerwy[3].
Rys.15.8. Zorientowany graf sieciowy obwodu elektrycznego z rys.15.1
Graf sieciowy musi być grafem skierowanym, silnie spójnym i nie zawierającym pętli własnych wierzchołków (węzłów).
15.1.3. Drzewo grafu i pojęcia pokrewne
Drzewem T grafu G nazywa się spójny podgraf grafu G zawierający wszystkie jego węzły i nie zawierający konturu.
Rys.15.9. Przykłady drzew (z całkowitej liczby 16 drzew) grafu z rys.15.8; a) ,
b) , c)
Konarami nazywa się krawędzie (gałęzie) drzewa. Między dwoma dowolnymi węzłami drzewa istnieje tylko jedna droga. Każde drzewo T grafu spójnego G zawiera dokładnie
(15.41)
konarów. Liczbę r nazywa się rzędem grafu G , tzn. .
Każdy graf spójny G zawiera co najmniej jedno drzewo.
Przeciwdrzewem (antydrzewem, zamknięciem) Z względem drzewa T grafu ...
frugo84