Co to jest Graf, do czego s┼éu┼╝y i jakie s─ů jego zastosowania?

Cz┼éowiek ma naturaln─ů tendencj─Ö do opisywania i porz─ůdkowania otaczaj─ůcego go ┼Ťwiata. W tym celu ludzko┼Ť─ç wymy┼Ťli┼éa wiele poj─Ö─ç s┼éu┼╝─ůcych do opisu ┼Ťwiata materialnego ÔÇô rzeczywistego mi─Ödzy innymi za pomoc─ů r├│┼╝nych parametr├│w. Zgodnie z t─ů ide─ů korzystamy z takich termin├│w jak wysoko┼Ť─ç, szeroko┼Ť─ç, d┼éugo┼Ť─ç, waga, kolor i tak dalej. Za ich pomoc─ů mo┼╝na opisa─ç wi─Ökszo┼Ť─ç otaczaj─ůcych nas obiekt├│w, jednak ten opis nie odzwierciedla jak poszczeg├│lne elementy s─ů ze sob─ů powi─ůzane oraz czy s─ů od siebie w jaki┼Ť spos├│b zale┼╝ne, czy te┼╝ wzgl─Ödem siebie uporz─ůdkowane. O ile przedstawiaj─ůc poszczeg├│lne przedmioty mo┼╝na za pomoc─ů mowy lub pisma opisa─ç ich relacje pomi─Ödzy sob─ů to na d┼éu┼╝sz─ů met─Ö jest to czasoch┼éonne. Dlatego w drodze do standaryzacji takich opis├│w i stworzenia mo┼╝liwo┼Ťci do sprawnego opisywania zale┼╝no┼Ťci pomi─Ödzy elementami powsta┼éo poj─Öcie grafu.

W ramach tego artyku┼éu postaram si─Ö Tobie przybli┼╝y─ç w przyst─Öpny spos├│b, bez zb─Ödnej teorii czym jest graf i jakie ma on zastosowania w dzisiejszym ┼Ťwiecie. Zacznijmy w takim razie od pocz─ůtku, czyli od zdefiniowania grafu jako poj─Öcia.

Co znajdziesz w tym wpisie?

Definicja Grafu

Graf jest poj─Öciem matematycznym, a dzia┼é zajmuj─ůcy si─Ö ich opisywaniem nazywany jest Teori─ů Graf├│w. Graf jest struktur─ů matematyczn─ů, za pomoc─ů kt├│rej przedstawia si─Ö relacje wyst─Öpuj─ůce pomi─Ödzy obiektami.

W takiej reprezentacji ka┼╝dy graf sk┼éada si─Ö z dw├│ch zbior├│w. Pierwszy z nich to zbi├│r wierzcho┼ék├│w, gdzie ka┼╝dy z nich jest pojedynczym obiektem. Drugi z nich to zbi├│r kraw─Ödzi, a ka┼╝da z nich opisuje dok┼éadnie jedn─ů relacj─Ö pomi─Ödzy dwoma obiektami.

Jeszcze bardziej upraszczaj─ůc je┼Ťli w czasie m┼éodo┼Ťci wykonywa┼ée┼Ť zadania w stylu ‘po┼é─ůcz (ponumerowane) kropki’ to tworzy┼ée┼Ť graficzn─ů reprezentacj─Ö pewnego grafu ÔÇô tworzonego rysunku. Dobrze jest pami─Öta─ç, ┼╝e ka┼╝da kraw─Öd┼║, podobnie jak wierzcho┼éek te┼╝ mo┼╝e mie─ç przypisan─ů warto┼Ť─ç (na przyk┼éad odleg┼éo┼Ť─ç mi─Ödzy dwoma punktami).

Przykład reprezentacji graficznej grafu
Przykład reprezentacji graficznej grafu

Kontynuuj─ůc przyk┼éad z ┼é─ůczeniem kropek w grafach istotny jest spos├│b po┼é─ůczenia pomi─Ödzy poszczeg├│lnymi wierzcho┼ékami. Dok┼éadniej w niekt├│rych przypadkach sama kolejno┼Ť─ç / kierunek ┼é─ůczenia poszczeg├│lnych wierzcho┼ék├│w ma znaczenie poniewa┼╝ mo┼╝na w ten spos├│b odda─ç spos├│b relacji mi─Ödzy obiektami. Dlatego wyr├│┼╝nia si─Ö podstawowe dwa rodzaje graf├│w: skierowane oraz nieskierowane.

Czym jest graf skierowany?

Graf skierowany to taki, w kt├│rym okre┼Ťlony jest kierunek przej┼Ťcia pomi─Ödzy wierzcho┼ékami. Takie grafy stosuje si─Ö w przypadkach, gdy kolejno┼Ť─ç zaistnienia danych obiekt├│w czy te┼╝ proces├│w opisywanych ma znaczenie. Innym przypadkiem stosowania graf├│w skierowanych s─ů sytuacje gdy opisywane s─ů procesy / zmiany nieodwracalne lub mo┼╝liwo┼Ť─ç przej┼Ťcia w jedn─ů stron─Ö jest mo┼╝liwa a w drug─ů ju┼╝ nie. W reprezentacji graficznej oznacza si─Ö to za pomoc─ů strza┼éki, kt├│rej grot jest skierowany do docelowego wierzcho┼éka.

Przyk┼éadem zastosowani grafu skierowanego mo┼╝e by─ç opis przepisu na przyrz─ůdzenie jajecznicy:

  1. Przygotuj patelni─Ö
  2. W┼é─ůcz palnik
  3. Dodaj masło
  4. Dodaj rozbite jajka
  5. Mieszaj
  6. Wy┼é─ůcz palnik
Prezentacja graficzna grafu skierowanego na przykładzie przepisu na jajecznicę
Przykład graficznej prezentacji grafu skierowanego

Dla obranej kolejno┼Ťci wykonywania poszczeg├│lnych etap├│w przepis mo┼╝e by─ç zapisany jako graf skierowany, ze wzgl─Ödu na konieczno┼Ť─ç zachowania kolejno┼Ťci proces├│w. Warto zwr├│ci─ç uwag─Ö, ┼╝e r├│wnie dobrze taki przepis m├│g┼éby by─ç uproszczonym algorytmem. W pewnym uog├│lnieniu mo┼╝na przyj─ů─ç, ┼╝e ka┼╝dy algorytm mo┼╝na opisa─ç za pomoc─ů grafu, co jest cz─Östym przyk┼éadem zastosowa┼ä graf├│w w celu ulepszenia, dopracowania, usprawnienia algorytm├│w lub przedstawienia ich graficznie w spos├│b uproszczony.

Czym jest graf nieskierowany?

Graf nieskierowany jest przeciwie┼ästwem poprzedniego rodzaju grafu. Stosuje si─Ö go, gdy kierunek relacji mi─Ödzy obiektami (wierzcho┼ékami) nie jest istotny lub z racji swojej natury jest dwukierunkowy. W taki spos├│b mo┼╝na opisa─ç na przyk┼éad domy przynale┼╝─ůce do wskazanej ulicy ÔÇô tworz─ůc graf miasta w kt├│rym poszczeg├│lne wierzcho┼éki to zar├│wno ulice jak i budynki. W takiej strukturze po┼é─ůczenie danej ulicy z budynkiem jest dwukierunkowe i mo┼╝na naturalnie pomi─Ödzy nimi si─Ö przemieszcza─ç (co ciekawe rozszerzenie tej struktury o pomieszczenia w budynkach z racji pomieszcze┼ä przechodnich nakazywa┼éoby zastosowanie grafu skierowanego).

Jakie znaczenie ma graf w matematyce ÔÇô Teoria Graf├│w

Dzia┼éem matematyki zajmuj─ůcym si─Ö grafami jest Teoria Graf├│w. Za jej pocz─ůtek uznaje si─Ö rozwi─ůzanie problemu most├│w kr├│lewieckich przez Leonharda Eulera w 1736 roku natomiast samego Eulera za prac─Ö kt├│r─ů przedstawi┼é jako ojca Teorii Graf├│w.

Czym by┼é problem most├│w kr├│lewieckich? Kr├│lewiec jest malowniczym miastem po┼éo┼╝onym nad rzek─ů Prego┼éa a w jej rozwidleniach le┼╝─ů dwie wyspy. ┼╗eby mo┼╝na by┼éo bezproblemowo przemieszcza─ç si─Ö pomi─Ödzy wyspami i stronami rzeki postawiono nad rzek─ů 7 most├│w. Problem, kt├│ry pr├│bowa┼é rozwik┼éa─ç Euler by┼é nast─Öpuj─ůcy: Czy da si─Ö przej┼Ť─ç kolejno przez wszystkie mosty w taki spos├│b aby ka┼╝dy z nich przekroczy─ç tylko raz? Euler w ramach swoich rozwa┼╝a┼ä udowodni┼é, ┼╝e nie jest to mo┼╝liwe a tak┼╝e opisa┼é uog├│lniony problem wskazuj─ůc jakie warunki musz─ů by─ç spe┼énione, aby da┼éo si─Ö w ten spos├│b przej┼Ť─ç ca┼éy powsta┼éy graf.

Rozmieszczenie most├│w kr├│lewieckich na mapie - wizualizacja pierwszego problemu Teorii Graf├│w
Rozmieszczenie most├│w kr├│lewieckich ÔÇô pierwszy problem teorii graf├│w

Ludzko┼Ť─ç spotyka jednak du┼╝o wi─Öksze problemy ni┼╝ to przez kt├│re mosty nale┼╝y przej┼Ť─ç. Dlatego w p├│┼║niejszym czasie dostrze┼╝ono ‘potencja┼é ekonomiczny’ w rozwa┼╝aniach Eulera. Na przyk┼éad problem komiwoja┼╝era, kt├│rego celem jest znalezienie najkr├│tszej, najta┼äszej lub najszybszej drogi pomi─Ödzy okre┼Ťlonymi punktami, przyjmuj─ůc ┼╝e zaczyna si─Ö ona i ko┼äczy w tym samym punkcie. Prze┼éo┼╝enie tego problemu na przyk┼éad na ilo┼Ť─ç paliwa, jakie zu┼╝yje kurier podczas rozwo┼╝enia paczek jest wystarczaj─ůcym powodem aby dog┼é─Öbniej analizowa─ç tego typu problemy.

Opr├│cz wspomnianych zastosowa┼ä sama teoria graf├│w sta┼éa si─Ö przyczynkiem do rozwoju jeszcze innej dziedziny matematyki ÔÇô topologii. Czym zajmuje si─Ö topologia, w skr├│cie badaniem w┼éasno┼Ťci obiekt├│w, kt├│re nie ulegn─ů ┼╝adnej zmianie nawet gdy si─Ö je w spos├│b znacz─ůcy zdeformuje. Nie zg┼é─Öbiaj─ůc si─Ö w szczeg├│┼éy mo┼╝na ┼╝artobliwie okre┼Ťli─ç, ┼╝e topologia zajmuje si─Ö tym jak nie rozr├│┼╝nia─ç kubka od obwarzanka.

Graf w informatyce i jego podstawowe zastosowania

Grafy opr├│cz wcze┼Ťniej wymienionych zastosowa┼ä optymalizacyjnych oraz zastosowa┼ä w takich dziedzinach jak elektronika czy te┼╝ chemia, cz─Östo s─ů wykorzystywane w informatyce. Warto zwr├│ci─ç uwag─Ö albo przynajmniej mie─ç ┼Ťwiadomo┼Ť─ç ich stosowania w sytuacjach z ┼╝ycia codziennego zw┼éaszcza w ┼Ťwiecie technologii internetowych.

Zastosowanie Graf├│w w drzewie DOM

Struktura pojedynczej strony internetowej jest mniej lub bardziej uporz─ůdkowana. Elementy najwy┼╝szego rz─Ödu (rodzice) zawieraj─ů elementy podrz─Ödne (dzieci), natomiast one posiadaj─ů swoje elementy i tak dalej. W celu uporz─ůdkowania takich struktur powsta┼é model DOM (Document Object Model). W uproszczeniu dzia┼éa on jak rosyjskie matrioszki, w wi─Ökszej matrioszce jest mniejsza a w niej nast─Öpna, z drobn─ů r├│┼╝nic─ů, ┼╝e ka┼╝da matrioszka mo┼╝e mie─ç niesko┼äczenie wiele podlegaj─ůcych jej matrioszek. Dzi─Öki przedstawieniu tej struktury za pomoc─ů grafu na przyk┼éad nieskierowanego, mo┼╝na w ┼éatwy spos├│b odnosi─ç si─Ö do konkretnych element├│w a tak┼╝e decydowa─ç, kt├│ry z nich ma by─ç wczytany jako pierwszy a kt├│re p├│┼║niej. Z pomoc─ů przegl─ůdarki ze struktury DOM danej strony internetowej mo┼╝na zaprezentowa─ç gotowy widok strony, kt├│r─ů chcia┼é zobaczy─ç u┼╝ytkownik.

Przykład DOM (Document Object Model) jako zastosowania grafu na przykładzie strony wp.pl
Przykład zastosowania DOM jako grafu na stronie wp.pl

Zastosowanie Graf├│w w strukturze strony internetowej

Zazwyczaj strona internetowa ma wi─Öcej ni┼╝ jedn─ů podstron─Ö. Wi─Ökszo┼Ť─ç z nich jest po┼é─ůczona pomi─Ödzy sob─ů aby mo┼╝na by┼éo p┼éynnie przechodzi─ç z jednej na drug─ů (na przyk┼éad za pomoc─ů menu). Ka┼╝de takie po┼é─ůczenie jest realizowane za pomoc─ů linku, kt├│ry ze swojej natury dzia┼éa jednokierunkowo, dlatego ka┼╝d─ů struktur─Ö strony mo┼╝na opisa─ç za pomoc─ů grafu skierowanego.

Zobacz też co to jest algorytm DFS i do czego służy!

Dlatego przedstawianie po┼é─ůcze┼ä mi─Ödzy podstronami w danej domenie jest realizowane w ten spos├│b mi─Ödzy innymi w celu przej┼Ťcia pomi─Ödzy wszystkimi zasobami na stronie. Realizuje si─Ö to w celu odnalezienia ewentualnych b┼é─Öd├│w na wszystkich podstronach, albo zebrania wszystkich tytu┼é├│w stron wyst─Öpuj─ůcych na stronach.

Przykład zastosowania grafu do przedstawienia struktury strony internetowej
Przykład zastosowania grafu do prezentacji struktury strony internetowej

W bardziej globalnej skali mo┼╝na w ten spos├│b zbiera─ç dane dotycz─ůce wszystkich stron internetowych jakie istniej─ů, o ile b─Ödzie si─Ö mia┼éo wystarczaj─ůco du┼╝o zasob├│w i mocy obliczeniowej.

Inne przypadki wykorzystania i stosowania graf├│w

Grafy same w sobie stosowane s─ů tak┼╝e w innych dziedzinach i p┼éaszczyznach ┼╝ycia. Popularny ostatnio Map Minding, do prezentowania map my┼Ťli jest te┼╝ procesem tworzenia i rysowania grafu. Projektowanie wszelkiego rodzaju proces├│w zachodz─ůcych w firmach, opracowywanie nowych cykli obiegu dokument├│w i rozbijanie ich na pomniejsze elementy aby znajdowa─ç punkty krytyczne, kt├│re mo┼╝na poprawi─ç to te┼╝ swojego rodzaju zastosowania teorii graf├│w i graf├│w samych w sobie.

Zastosowanie graf├│w w SEO

W kontek┼Ťcie samego SEO, pozycjonowania stron internetowych grafy maj─ů niebagatelne znaczenie, poniewa┼╝ ca┼éy internet teoretycznie da si─Ö opisa─ç za pomoc─ů jednego wielkiego grafu albo sieci wielu podgraf├│w. Maj─ůc tak─ů struktur─Ö mo┼╝na wzgl─Ödem ustalonych parametr├│w segregowa─ç poszczeg├│lne strony, czyli wyniki wyszukiwania, co jest celem w samym sobie wszystkich wyszukiwarek internetowych.

Dlatego te┼╝ zainteresowanie grafami przez ┼Ťwiat pozycjonowania jest do┼Ť─ç du┼╝e, ze wzgl─Ödu, ┼╝e algorytmy Google je wykorzystuj─ůce segreguj─ů wyniki na konkretne zapytania. Tak samo opieka nad odpowiednio du┼╝ym serwisem nie by┼éaby mo┼╝liwa je┼Ťli nie da┼éo by si─Ö w relatywnie kr├│tkim czasie sprawdzi─ç wszystkich zasob├│w strony internetowej.

Je┼Ťli poj─Öcie graf├│w by┼éo Tobie wcze┼Ťniej obce, mam nadziej─Ö, ┼╝e chocia┼╝ troch─Ö odpowiedzia┼éem na pytanie czym s─ů i do czego s─ů stosowane. Masz te┼╝ teraz ┼Ťwiadomo┼Ť─ç jak szerokie zastosowania one posiadaj─ů i by─ç mo┼╝e kolejne znajdziesz w rzeczach, kt├│re sam realizujesz.

FAQ

Co to jest graf?

Graf jest struktur─ů matematyczn─ů, za pomoc─ů kt├│rej przedstawia si─Ö relacje wyst─Öpuj─ůce pomi─Ödzy obiektami. Dowiedz si─Ö wi─Öcej o grafach z artyku┼éu !

Co to jest graf skierowany?

Graf skierowany to taki, w kt├│rym okre┼Ťlony jest kierunek przej┼Ťcia pomi─Ödzy wierzcho┼ékami. Dowiedz si─Ö wi─Öcej o grafach skierowanych z artyku┼éu !

Co to jest graf nieskierowany?

Graf nieskierowany stosuje się, gdy kierunek relacji między obiektami (wierzchołkami) nie jest istotny lub z racji swojej natury jest dwukierunkowy. Dowiedz się więcej o grafach nieskierowanych z artykułu !

Jakie s─ů zastosowania graf├│w?

Grafy maj─ů zastosowania w matematyce, informatyce i pokrewnych a tak┼╝e rozbie┼╝nych dziedzinach. Zobacz przyk┼éadowe zastosowania graf├│w !

Mo┼╝e Ci si─Ö r├│wnie┼╝ spodoba

1 Odpowied┼║

  1. Dominika pisze:

    Dobre pomys┼éy pewnie wykorzystam co┼Ť u siebie.

Dodaj komentarz

Tw├│j adres email nie zostanie opublikowany. Pola, kt├│rych wype┼énienie jest wymagane, s─ů oznaczone symbolem *