Teoria grafów

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ą:

  1. Zadanie najkrótszego łańcucha (wymiana sprzętu, rozmieszczenie karetek pogotowia i central telefonicznych).
  2. Problem maksymalnego przepływu (usprawnienie ruchu w sieci dynamicznej, dystrybucja pracy, organizacja przepustowości).
  3. Problem powłok i opakowań (rozmieszczenie centrów kontroli).
  4. Kolorowanie na wykresach (przydział pamięci na komputerach elektronicznych).
  5. 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.