Graf (matematyka)
struktura matematyczna opisująca zbiór obiektów z połączeniami niektórych par / Z Wikipedii, wolnej encyclopedia
Drogi AI, mówmy krótko, odpowiadając po prostu na te kluczowe pytania:
Czy możesz wymienić najważniejsze fakty i statystyki dotyczące Graf (matematyka)?
Podsumuj ten artykuł dla 10-latka
Graf – podstawowy obiekt rozważań teorii grafów[1][2] , struktura matematyczna służąca do przedstawiania i badania relacji między obiektami[3] [4] . W uproszczeniu graf to zbiór wierzchołków, które mogą być połączone krawędziami w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków[5].
Zobacz też: inne znaczenia wyrazu „graf”. |
Wierzchołki grafu mogą być numerowane i czasem stanowią reprezentację jakichś obiektów, natomiast krawędzie mogą wówczas obrazować relacje między takimi obiektami[6]. Wierzchołki należące do krawędzi nazywane są jej końcami[7]. Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie nazywany jest grafem skierowanym[8] lub orgrafem[9]. Krawędź grafu może posiadać wagę, to znaczy przypisaną liczbę, która określa na przykład odległość między wierzchołkami (jeśli np. graf jest reprezentacją połączeń między miastami)[10]. W grafie skierowanym wagi mogą być zależne od kierunku przechodzenia przez krawędź (np. jeśli graf reprezentuje trud poruszania się po jakimś terenie, to droga pod górkę będzie miała przypisaną większą wagę niż z górki)[11].
Za pierwszego teoretyka i badacza grafów uważa się[12] szwajcarskiego matematyka i fizyka Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich. Pierwsze użycie określenia „graf” przypisywane jest Jamesowi Josephowi Sylvesterowi – matematykowi angielskiego pochodzenia[13].