Teoria grafów - wprowadzenie

W dziedzinie matematyki i informatyki teoria grafów to nauka o grafach, która dotyczy relacji między krawędziami i wierzchołkami . Jest to popularny przedmiot mający swoje zastosowania w informatyce, informatyce, naukach biologicznych, matematyce i językoznawstwie, by wymienić tylko kilka. Bez zbędnych ceregieli zacznijmy od zdefiniowania wykresu.

Co to jest wykres?

Wykres jest obrazowym przedstawieniem zbioru obiektów, w którym niektóre pary obiektów są połączone linkami. Połączone obiekty są reprezentowane przez punkty określane jakovertices, a łącza łączące wierzchołki są nazywane edges.

Formalnie wykres jest parą zbiorów (V, E), gdzie Vjest zbiorem wierzchołków, a E jest zbiorem krawędzi, łączących pary wierzchołków. Spójrz na poniższy wykres -

Na powyższym wykresie

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

Zastosowania teorii grafów

Teoria grafów ma swoje zastosowania w różnych dziedzinach inżynierii -

Electrical Engineering- Pojęcia teorii grafów są szeroko stosowane w projektowaniu połączeń obwodów. Typy lub organizacja połączeń nazywane są topologiami. Niektóre przykłady topologii to topologie gwiazdy, mostka, szeregowe i równoległe.

Computer Science- Teoria grafów służy do badania algorytmów. Na przykład,

• Algorytm Kruskala
• Algorytm Prima
• Algorytm Dijkstry

Computer Network - Relacje między połączonymi komputerami w sieci są zgodne z zasadami teorii grafów.

Science - Strukturę molekularną i strukturę chemiczną substancji, strukturę DNA organizmu itp. Przedstawiają wykresy.

Linguistics - Drzewo parsowania języka i gramatyki języka wykorzystuje wykresy.

General- Trasy między miastami można przedstawić za pomocą wykresów. Przedstawienie hierarchicznie uporządkowanych informacji, takich jak drzewo genealogiczne, może być użyte jako specjalny typ wykresu zwany drzewem.