Teoria grafów jest jednym z podrozdziałów.matematyka, której główną cechą wyróżniającą jest metoda geometryczna w badaniu obiektów. Jego założycielem jest znany matematyk L. Euler.
Zastosowanie teorii grafów do końca XIX wiekusprowadził się do rozwiązywania zabawnych problemów i nie przyciągnął znaczącej uwagi ogólnej. Od XX wieku, kiedy teoria grafów została przekształcona w niezależną dyscyplinę matematyczną, znalazła szerokie zastosowanie w takich dziedzinach nauki, jak cybernetyka, fizyka, logistyka, programowanie, biologia, elektronika, systemy transportu i komunikacji.
Podstawowe pojęcia teorii grafów
Podstawą jest wykres.W terminologii można spotkać taką koncepcję, jak sieć identyczna z wykresem. Ta ostatnia jest niepustą liczbą punktów, to znaczy wierzchołkami i segmentami, to znaczy krawędziami, których oba końce odpowiadają określonej liczbie punktów. Teoria grafów nie ma żadnego sensu w wartościach krawędzi i wierzchołków. Na przykład łączące je miasta i drogi, gdzie pierwsze to wierzchołki wykresu, a drugie to krawędzie. Teoretycznie większe znaczenie mają łuki. Jeśli krawędź ma kierunek, to ma nazwę łuku, a jeśli wykres z zorientowanymi krawędziami, nazywa się to wykresem.
W terminologii teorii wyróżnia się również następujące pojęcia:
Podgraf to wykres, którego wszystkie krawędzie i wierzchołki znajdują się między wierzchołkami i krawędziami.
Połączony wykres to jeden z łańcuchem łączącym je dla dwóch różnych wierzchołków.
Ważony połączony wykres to wykres z funkcją wagi.
Drzewo jest połączonym wykresem bez cykli.
Szkielet to podgraf, który jest drzewem.
Podczas drukowania wykresu na płaszczyźniepewien zapis: wybrany wierzchołek odpowiada punktowi na najprostszej powierzchni, a jeśli między wierzchołkami znajduje się krawędź, wówczas odpowiednie punkty są połączone segmentem. Jeśli wykres jest zorientowany, segmenty te są zastępowane strzałkami.
Ale nie porównuj z nim obrazu wykresusami, tj. o strukturze abstrakcyjnej, ponieważ więcej niż jedna reprezentacja graficzna może być nadana jednemu wykresowi. Rysunek na płaszczyźnie podano, aby zobaczyć, które pary wierzchołków są połączone krawędziami, a które nie.
Wśród niektórych problemów teorii grafów są:
- Zadanie najkrótszego łańcucha (wymiana sprzętu, rozmieszczenie karetek pogotowia i central telefonicznych).
- Problem maksymalnego przepływu (usprawnienie ruchu w sieci dynamicznej, dystrybucja pracy, organizacja przepustowości).
- Problem powłok i opakowań (rozmieszczenie centrów kontroli).
- Kolorowanie na wykresach (przydział pamięci na komputerach elektronicznych).
- Sieci komunikacyjne i wykresy (tworzenie sieci komunikacyjnej, analiza sieci komunikacyjnych).
Obecnie nie jest możliwe zaprogramowanie większości zadań bez znajomości teorii grafów. Ułatwia to i upraszcza pracę z komputerami.
Programowanie wykorzystuje wiele struktur iuniwersalne metody rozwiązywania problemów, a jedną z nich jest teoria grafów. Jego wartość trudno przecenić. Teoria grafów w programowaniu pozwala uprościć wyszukiwanie informacji, optymalizować programy, konwertować i dystrybuować dane. Dzięki algorytmom teorii możliwe staje się ich wykorzystanie i ocena w celu rozwiązania określonych problemów, modyfikacji algorytmu bez zmniejszania stopnia matematycznej niezawodności ostatecznej wersji programu.
Ważna właściwość systemu lub modelu sterowaniajest zbiorem relacji binarnych w zestawie akcji i jednostek danych. Struktury te są jedynymi częściami programów i informacji, które przekształcają. Dlatego wykresy są podstawą konstrukcji dla programisty.
