Graf prosty – graf złożony ze skończonej liczby wierzchołków oraz krawędzi bez pętli własnych i krawędzi podwójnych lub wielokrotnych.
Często określenie graf (bez przymiotników) oznacza właśnie po prostu: graf prosty. Jednocześnie każdy graf prosty jest grafem, ale nie każdy graf jest grafem prostym.
Własności i twierdzenia
Definicja Dla grafu prostego , zbiór krawędzi jest skończonym zbiorem dwuelementowych podzbiorów . Równoważnie, możemy powiedzieć, że jest to taki graf , że .
Jeśli graf jest prosty o liczbie wierzchołków to zachodzą następujące własności:
Graf jest drzewem, czyli jest spójny i nie ma cykli. Graf jest spójny i ma krawędzi. Graf ma krawędzi i nie ma cykli.
Twierdzenie Diraca Graf prosty , takie że oraz jest hamiltonowski.
Twierdzenie Orego Graf prosty , taki że oraz z nierównością zachodzącą dla każdej pary niepołączonych krawędzią wierzchołków posiada cykl Hamiltona.
Izomorfizm Grafy proste oraz są izomorficzne, jeśli istnieje bijekcja taka, że .
Przykłady grafów prostych
Zobacz też teoria grafów klasa grafów graf pełny
Przypisy
Linki zewnętrzne [dostęp 2025-10-12].
P