A Grafy nieskierowane : Wykres, w którym krawędzie nie mają kierunku, tj. Krawędzie nie mają strzałek wskazujących kierunek przechodzenia. Przykład: wykres sieci społecznościowej, na którym przyjaźnie nie są kierunkowe.

Grafy skierowane : Wykres, w którym krawędzie mają kierunek, tj. krawędzie mają strzałki wskazujące kierunek przechodzenia. Przykład: wykres strony internetowej, na którym łącza między stronami są kierunkowe.

Wykresy ważone: Wykres, na którym krawędziom przypisane są wagi lub koszty. Przykład: Wykres sieci drogowej, na którym wagi mogą przedstawiać odległość między dwoma miastami.

Nieważony wykres s: Wykres, w którym krawędzie nie mają przypisanych wag ani kosztów. Przykład: wykres sieci społecznościowej, którego krawędzie przedstawiają przyjaźnie.

Kompletne wykresy: Graf, w którym każdy wierzchołek jest połączony z każdym innym wierzchołkiem. Przykład: Wykres turnieju, na którym każdy gracz gra przeciwko każdemu innemu graczowi.

Wykresy dwudzielne: Graf, w którym wierzchołki można podzielić na dwa rozłączne zbiory w taki sposób, że każda krawędź łączy wierzchołek z jednego zbioru z wierzchołkiem z drugiego zbioru. Przykład: Wykres kandydatów do pracy, którego wierzchołki można podzielić na kandydatów i oferty pracy.

Drzewa : Połączony graf bez cykli. Przykład: drzewo genealogiczne, w którym każda osoba jest powiązana ze swoimi rodzicami.

Cykle : Wykres z co najmniej jednym cyklem. Przykład: Wykres udostępniania rowerów, na którym rowery reprezentują trasy, którymi pokonują rowery.

Rzadkie wykresy: Graf o stosunkowo małej liczbie krawędzi w porównaniu z liczbą wierzchołków. Przykład: Wykres reakcji chemicznej, w którym każdy wierzchołek reprezentuje związek chemiczny, a każda krawędź reprezentuje reakcję między dwoma związkami.

Gęsty wykres s: Graf o wielu krawędziach w porównaniu z liczbą wierzchołków. Przykład: wykres sieci społecznościowej, w którym każdy wierzchołek reprezentuje osobę, a każda krawędź reprezentuje przyjaźń.

Rodzaje wykresów:

1. Grafy skończone

Graf nazywamy skończonym, jeśli ma skończoną liczbę wierzchołków i skończoną liczbę krawędzi. Graf skończony to graf o skończonej liczbie wierzchołków i krawędzi. Innymi słowy, zarówno liczba wierzchołków, jak i liczba krawędzi w skończonym grafie są ograniczone i można je policzyć. Grafy skończone są często używane do modelowania sytuacji w świecie rzeczywistym, w których istnieje ograniczona liczba obiektów i relacji między nimi

2. Nieskończony wykres:

Graf nazywamy nieskończonym, jeśli ma nieskończoną liczbę wierzchołków i nieskończoną liczbę krawędzi.

3. Trywialny wykres:

Mówi się, że graf jest trywialny, jeśli skończony graf zawiera tylko jeden wierzchołek i nie ma krawędzi. Graf trywialny to graf mający tylko jeden wierzchołek i pozbawiony krawędzi. Nazywa się go również wykresem singletonowym lub wykresem pojedynczego wierzchołka. Wykres trywialny jest najprostszym typem wykresu i często jest używany jako punkt wyjścia do tworzenia bardziej złożonych wykresów. W teorii grafów trywialne wykresy są uważane za przypadek zdegenerowany i zazwyczaj nie są badane szczegółowo

zamów losowo w sql

4. Prosty wykres:

Graf prosty to graf, który nie zawiera więcej niż jednej krawędzi pomiędzy parą wierzchołków. Przykładem prostego wykresu jest prosty tor kolejowy łączący różne miasta.

5. Wielu wykresów:

Każdy graf, który zawiera pewne równoległe krawędzie, ale nie zawiera żadnej pętli własnej, nazywany jest multigrafem. Na przykład mapa drogowa.

• Krawędzie równoległe: Jeśli dwa wierzchołki są połączone więcej niż jedną krawędzią, to takie krawędzie nazywane są krawędziami równoległymi, które mają wiele tras, ale jeden cel.
• Pętla: Krawędź grafu rozpoczynająca się od wierzchołka i kończąca się w tym samym wierzchołku nazywana jest pętlą lub pętlą własną.

6. Wykres zerowy:

Graf rzędu n i o rozmiarze zerowym to graf, w którym występują tylko izolowane wierzchołki bez krawędzi łączących jakąkolwiek parę wierzchołków. Graf zerowy to graf bez krawędzi. Innymi słowy, jest to graf zawierający tylko wierzchołki i brak połączeń między nimi. Wykres zerowy można również nazwać wykresem bez krawędzi, wykresem izolowanym lub wykresem dyskretnym

7. Pełny wykres:

Graf prosty mający n wierzchołków nazywany jest grafem pełnym, jeśli stopień każdego wierzchołka wynosi n-1, to znaczy, że jeden wierzchołek jest połączony z n-1 krawędziami lub pozostałymi wierzchołkami grafu. Pełny wykres nazywany jest także pełnym wykresem.

8. Pseudowykres:

Graf G zawierający pętlę własną i kilka krawędzi wielokrotnych nazywany jest pseudografem. Pseudograf to rodzaj grafu, który pozwala na istnienie pętli własnych (krawędzi łączących wierzchołek z samym sobą) i wielu krawędzi (więcej niż jedna krawędź łącząca dwa wierzchołki). Natomiast prosty wykres to wykres, który nie pozwala na pętle ani wiele krawędzi.

9. Regularny wykres:

Graf prosty nazywamy regularnym, jeżeli wszystkie wierzchołki grafu G są równego stopnia. Wszystkie kompletne wykresy są regularne, ale odwrotnie nie jest możliwe. Graf regularny to rodzaj grafu nieskierowanego, w którym każdy wierzchołek ma taką samą liczbę krawędzi lub sąsiadów. Innymi słowy, jeśli graf jest regularny, to każdy wierzchołek ma ten sam stopień.

10. Wykres dwudzielny:

Graf G = (V, E) nazywa się grafem dwudzielnym, jeśli jego zbiór wierzchołków V(G) można podzielić na dwa niepuste rozłączne podzbiory. V1(G) i V2(G) w taki sposób, że każda krawędź e E(G) ma jeden koniec w V1(G) i drugi koniec w V2(G). Podział V1 U V2 = V nazywany jest dwustronnym G. Tutaj na rysunku: V1(G)={V5, V4, V3} i V2(G)={V1, V2}

11. Wykres oznaczony:

Jeśli wierzchołki i krawędzie grafu są oznaczone nazwą, datą lub wagą, wówczas nazywa się to wykresem etykietowanym. Nazywa się go również wykresem ważonym.

12. Wykres dwuznakowy:

Graf G = (V, E) z odwzorowaniem f takim, że każda krawędź jest odwzorowana na jakąś uporządkowaną parę wierzchołków (Vi, Vj) nazywa się digrafem. Nazywa się to również Kierowany wykres . Uporządkowana para (Vi, Vj) oznacza krawędź pomiędzy Vi i Vj ze strzałką skierowaną od Vi do Vj. Tutaj na rysunku: e1 = (V1, V2) e2 = (V2, V3) e4 = (V2, V4)

13. Podpunkt:

Wykres G1 = (V1, E1) nazywany jest podgrafem grafu G(V, E), jeśli V1(G) jest podzbiorem V(G) i E1(G) jest podzbiorem E(G) tak, że każda krawędź G1 ma takie same wierzchołki końcowe jak w G.

14. Wykres połączenia lub rozłączenia:

Graf G nazywamy spójnym, jeżeli dowolna para wierzchołków (Vi, Vj) grafu G jest osiągalna między sobą. Lub mówimy, że graf jest spójny, jeśli istnieje co najmniej jedna ścieżka pomiędzy każdą parą wierzchołków w grafie G, w przeciwnym razie jest on rozłączony. Graf zerowy o n wierzchołkach to graf rozłączony składający się z n składowych. Każdy komponent składa się z jednego wierzchołka i nie ma krawędzi.

gimp zmienia kolor

15. Wykres cykliczny:

Graf G składający się z n wierzchołków i n> = 3 czyli V1, V2, V3- – – – Vn oraz krawędzi (V1, V2), (V2, V3), (V3, V4)- – – – (Vn, V1) nazywane są grafami cyklicznymi.

16. Rodzaje podgrafów:

• Podgraf rozłączny wierzchołków: Mówi się, że dowolne dwa grafy G1 = (V1, E1) i G2 = (V2, E2) są rozłącznymi wierzchołkami grafu G = (V, E), jeśli przecięcie V1(G1) V2(G2) = zero. Na rysunku nie ma wspólnego wierzchołka pomiędzy G1 i G2.
• Podgraf rozłączny krawędziowo: Mówi się, że podgraf jest rozłączny od krawędzi, jeśli przecięcie E1(G1) E2(G2) = null. Na rysunku nie ma wspólnej krawędzi pomiędzy G1 i G2.

Notatka: Podgraf rozłączny krawędziowo może mieć wspólne wierzchołki, ale graf rozłączny wierzchołkowo nie może mieć wspólnej krawędzi, zatem podgraf rozłączny wierzchołkowo będzie zawsze podgrafem rozłącznym krawędziowo.

17. Podgraf rozpinający

Rozważmy wykres G(V,E), jak pokazano poniżej. Podgraf rozpinający to podgraf zawierający wszystkie wierzchołki pierwotnego grafu, czyli G'(V',E'), który jest rozpinany, jeśli V'=V i E' jest podzbiorem E.

Zatem jeden z podgrafów rozpinających może wyglądać jak pokazano poniżej G’(V’,E’). Ma wszystkie wierzchołki pierwotnego grafu G i niektóre krawędzie G.

To tylko jeden z wielu podgrafów rozpinających grafu G. Możemy tworzyć różne inne podgrafy rozpinające poprzez różne kombinacje krawędzi. Zauważ, że jeśli weźmiemy pod uwagę graf G'(V',E'), gdzie V'=V i E'=E, to graf G' jest podgrafem rozpinającym grafu G(V,E).

Zalety wykresów:

1. Grafów można używać do modelowania i analizowania złożonych systemów i relacji.
2. Są przydatne do wizualizacji i zrozumienia danych.
3. Algorytmy grafowe są szeroko stosowane w informatyce i innych dziedzinach, takich jak analiza sieci społecznościowych, logistyka i transport.
4. Wykresy mogą służyć do reprezentowania szerokiego zakresu typów danych, w tym sieci społecznościowych, sieci drogowych i Internetu.

Wady wykresów:

1. Duże wykresy mogą być trudne do wizualizacji i analizy.
2. Algorytmy graficzne mogą być kosztowne obliczeniowo, szczególnie w przypadku dużych wykresów.
3. Interpretacja wyników wykresów może być subiektywna i może wymagać wiedzy specyficznej dla danej dziedziny.
4. Wykresy mogą być podatne na szumy i wartości odstające, co może mieć wpływ na dokładność wyników analizy.

Powiązany artykuł: Zastosowania, zalety i wady wykresu