Μετάβαση στο περιεχόμενο

Μηδενικός γράφος

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μηδενικός γράφος
Μηδενικός γράφος 7 κόμβους
Κορυφές
Ακμές
Ακτίνα
Διάμετρος
Περιφέρεια
Αυτομορφισμοίn! (Sn)
Χρωματικός αριθμός
Ιδιότητες
Πίνακας γράφων και των παραμέτρων τους

Στην θεωρία γράφων, μηδενικός γράφος είναι ένας γράφος χωρίς ακμές. Πιο συγκεκριμένα, ο γράφος είναι μηδενικός ανν .[1]:7[2]

  • Το συμπλήρωμα του μηδενικού γράφου είναι ο πλήρης γράφος.
  • Ο μηδενικός γράφος μπορεί να χρωματιστεί με ένα χρώμα, αφού δεν υπάρχουν ακμές μεταξύ των κόμβων του. Το χρωματικό πολυώνυμο του γράφου είναι , αφού όλοι οι χρωματισμοί μπορούν να γίνουν ανεξάρτητα.
  • Σε έναν μηδενικό γράφο όλες οι αποστάσεις μεταξύ διαφορετικών κορυφών είναι , επομένως η ακτίνα, η διάμετρος και η περιφέρεια είναι .
  • Ο πίνακας γειτνίασης του μηδενικού γράφου είναι ο μηδενικός πίνακας.
  1. Μανωλόπουλος, Ιωάννης. «Θεωρία και Αλγόριθμοι Γράφων: Εισαγωγή (Ορισμοί)» (PDF). Τμήμα Πληροφορικής, Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης. Ανακτήθηκε στις 16 Ιανουαρίου 2024. 
  2. «Βασικοί ορισμοί» (PDF). Πανεπιστήμιο Αιγαίου. Ανακτήθηκε στις 16 Ιανουαρίου 2024.