Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1i7iOpistopologicznyukładówhydraulicznychiZastosowanieteoriigrafów
37
Teoriagrafów
4)dostarczaodpowiednichtwierdzeńimetodprzydatnychdo
automatycznegoodwzorowywaniapołączeńwsieciwodociągowejdlapotrzeb
komputerowejrealizacjiobliczeń.Wzwiązkuztymwp.1.7.2będzieprzedsta-
wionezestawienienajbardziejprzydatnychpojęćitwierdzeńteoriigrafów.Wy-
korzystująctepojęciaitwierdzenia,możnazauważyć,żeponiższetrzyzagad-
nieniasprowadzająsiędoodpowiednichzagadnieńteoriigrafów[2,5,10]:
1)wyznaczeniapewnejklasygrafównieizomorficznychdlazadanychliczb
min;gdziemoznaczaliczbęprzewodówsieci,an-liczbęjejwęzłów;
3)wyznaczeniawszystkichmaksymalnychdrzewsieci;
4)wyznaczeniaoptymalnejrodzinypodstawowychcykligrafu,minimalizu-
jącychczasobliczeń.
Zagadnieniatebędąomówionewkolejnychpunktach1.7.3÷1.7.5.
1.7.2.Podstawowedefinicjeitwierdzeniateoriigrafów
Omówieniewyżejsformułowanychzagadnieńwymagawstępnegowprowadze-
niaodpowiednichdefinicjiitwierdzeńteoriigrafów[2,5,10].
Rozszerzającdefinicjęgrafu,możnazauważyć,żewgrafiedwaróżne
punktysązesobąpołączonejednąliniąlubkilkomaliniami-prostymilub
krzywymi,któresąnazywanełukamilubkrawędziami,natomiastpunktyteto
węzłylubwierzchołki.Krawędzie,którełączątesamedwawęzły,sąnazywane
równoległymi.Węzłypołączonekrawędziątowęzłykrańcowekrawędzi.
Incydencja
5)elementówgrafu:dwaróżnewęzłygrafunazywamyincy-
dentnymi,gdysąpołączoneconajmniejjednąkrawędzią;dwiekrawędziesą
incydentne,gdymająwspólnywęzeł;krawędźnazywamyincydentnązwęzłem,
gdyjestwęzłemkrańcowymtejkrawędzi.
DwagrafyGiG′uważasięzawzajemnieizomorficzneczylirównoważ-
ne,jeślimająidentycznewłasnościwsensieteoriigrafów,tzn.jeślizachodzi
wzajemniejednoznacznaodpowiedniośćmiędzywierzchołkamiorazmiędzyich
krawędziami,przyzachowaniurelacjiincydencji.Naprzykładmożnaspraw-
dzić,żegrafyprzedstawionenarys.1.8sąizomorficzne,gdyżistniejeodpo-
wiedniośćmiędzyodpowiednimiwęzłamiikrawędziami.Zdefinicjiizomorfi-
zmuwynika,żedwagrafyizomorficznemusząmieć:
•takąsamąliczbęwierzchołków,
4)Pojęciegrafuwprowadziłw1736r.LeonardEuler(1707-1783)wpublikacjint.tzw.za-
gadnieniamostówkrólewieckich,którąuważasięzapoczątekteoriigrafów;dopierow1847r.
G.R.Kirchhoff(1824-1887)wdwóchfundamentalnychpublikacjachprzedstawiłteoriędrzewdo
zastosowańwobwodachelektrycznych[1].
5)Incydencja-wgeometriiwłasnośćokreślonychrelacjiwzajemnychmiędzypewnymifi-
guramilubprzynależności,np.incydencjaprostejipunktuoznacza,żepunktleżynaprostejlub
prostaprzechodziprzezpunkt;wgrafie,jeśliwierzchołekWjestwierzchołkiemkońcowymkra-
wędzie,tomówimy,żeWiesąincydentnezesobąlubdosiebie.
