{"id":252,"date":"2024-02-28T22:43:07","date_gmt":"2024-02-28T21:43:07","guid":{"rendered":"http:\/\/cyberszary.pl\/?p=252"},"modified":"2024-05-13T22:08:31","modified_gmt":"2024-05-13T20:08:31","slug":"grafy-to-nie-tylko-laczenie-kropek-kreskami","status":"publish","type":"post","link":"https:\/\/cyberszary.pl\/index.php\/2024\/02\/28\/grafy-to-nie-tylko-laczenie-kropek-kreskami\/","title":{"rendered":"Grafy. To nie tylko \u0142\u0105czenie kropek kreskami :)"},"content":{"rendered":"
\"\"<\/figure>\n\n\n

<\/p>\n\n\n\n

Przegl\u0105daj\u0105c Internet ka\u017cdy z nas na jakim\u015b etapie natkn\u0105\u0142 si\u0119 na wizualn\u0105 reprezentacj\u0119 grafu. Takie k\u00f3\u0142eczka (w\u0142a\u015bciwie wierzcho\u0142ki), po\u0142\u0105czone kreseczkami (w\u0142a\u015bciwie kraw\u0119dziami). In\u017cynierowie s\u0105 bardziej z grafami zapoznani, lecz dla wi\u0119kszo\u015bci jest to zwykle nieczytelny rysunek, jak np. taki: <\/p>\n\n\n\n

\"graf\"
Przyk\u0142ad grafu, \u017ar\u00f3d\u0142o: opracowanie w\u0142asne<\/figcaption><\/figure>\n\n\n\n

Jednak\u017ce, pomimo swojego niepozornego graficznego przedstawienia, s\u0105 niezwykle pomocne. Pewnie ka\u017cdemu z nas, przynajmniej raz zdarzy\u0142o si\u0119 korzysta\u0107 z nawigacji samochodowej. Podczas wyznaczania najkr\u00f3tszej trasy pomi\u0119dzy miejscem w kt\u00f3rym si\u0119 znajdujemy a docelowym, to w\u0142a\u015bnie algorytm oparty na teorii graf\u00f3w wyszuka\u0142 nam odpowiedni\u0105 tras\u0119. Wi\u0119c, co to s\u0105 te grafy?<\/p>\n\n\n\n

<\/p>\n\n\n\n

Wst\u0119p<\/strong><\/h4>\n\n\n\n

Najpro\u015bciej m\u00f3wi\u0105c, graf to pewnego rodzaju obiekt. Obiektu posiadaj\u0105cego wierzcho\u0142ki oraz \u0142\u0105cz\u0105ce je linie zwane kraw\u0119dziami. By by\u0107 bardziej szczeg\u00f3\u0142owym – m\u00f3wi\u0105c j\u0119zykiem matematyki – graf to zbi\u00f3r obiekt\u00f3w (w\u0119z\u0142\u00f3w) po\u0142\u0105czonych relacjami (kraw\u0119dziami). A wi\u0119c ka\u017cd\u0105 relacj\u0119 pomi\u0119dzy obiektami mo\u017cemy zaprezentowa\u0107 graficznie za pomoc\u0105 grafu. Je\u017celi ka\u017cdej kraw\u0119dzi grafu przypiszemy pewn\u0105 wag\u01191<\/a><\/sup> kt\u00f3ra mo\u017ce okre\u015bla\u0107 r\u00f3\u017cne parametry (np. wierzcho\u0142ki s\u0105 miastami, a kraw\u0119dzie je \u0142\u0105cz\u0105ce symbolizuj\u0105 drog\u0119 pomi\u0119dzy nimi, to waga oznacza odleg\u0142o\u015b\u0107 pomi\u0119dzy miastami).<\/p>\n\n\n\n

<\/p>\n\n\n\n

Graf skierowany<\/strong><\/h5>\n\n\n\n

Graf skierowany sk\u0142ada si\u0119 z dw\u00f3ch zbior\u00f3w \u2013 niepustego zbioru wierzcho\u0142k\u00f3w V oraz rodziny A par uporz\u0105dkowanych element\u00f3w zbioru V zwanych kraw\u0119dziami lub \u0142ukami grafu skierowanego. <\/p>\n\n\n\n

G_s = \\langle V, A \\rangle<\/pre><\/div>\n\n\n\n
gdzie:<\/p>\n\n\n\n
A \\subset V x V<\/pre><\/div>\n\n\n\n
<\/p>\n\n\n\n
Graf nieskierowany<\/strong><\/h5>\n\n\n\n
Graf skierowany sk\u0142ada si\u0119 z dw\u00f3ch zbior\u00f3w \u2013 niepustego zbioru wierzcho\u0142k\u00f3w V oraz rodziny dwuelementowych E  uporz\u0105dkowanych element\u00f3w zbioru V zwanych kraw\u0119dziami. Elementy V oraz E nie musz\u0105 by\u0107 sko\u0144czone. <\/p>\n\n\n\n
G = \\langle V, E \\rangle<\/pre><\/div>\n\n\n\n
gdzie:<\/p>\n\n\n\n
E \\subset \\lbrace \\lbrace x,y \\rbrace \\subset V \\rbrace<\/pre><\/div>\n\n\n\n
<\/p>\n\n\n\n
Graf wa\u017cony<\/strong><\/h5>\n\n\n\n
Graf wa\u017cony, to graf w kt\u00f3rym kraw\u0119dziom (lub \u0142ukom) zosta\u0142a przypisana pewna warto\u015b\u0107 liczbowa \/ etykieta  (waga) s\u0142u\u017c\u0105ca do przechowywania dodatkowych informacji o relacjach. <\/p>\n\n\n\n
<\/p>\n\n\n\n
obja\u015bnienie symboli: <\/strong><\/p>\n\n\n\n
V – zbi\u00f3r wierzcho\u0142\u00f3w N=|V|<\/p>\n\n\n\n
E – zbi\u00f3r kraw\u0119dzi <\/p>\n\n\n\n
A – zbi\u00f3r \u0142uk\u00f3w (kraw\u0119dzi skierowanych) <\/p>\n\n\n\n
<\/p>\n\n\n\n
Wykorzystanie graf\u00f3w<\/strong><\/h5>\n\n\n\n
Grafy mog\u0105 by\u0107 wykorzystywane do rozwi\u0105zywania szereg\u00f3w problem\u00f3w: <\/p>\n\n\n\n