Προβλήματα Μαθηματικών

Οκτώβριος 12, 2018

Απλά γραφήματα

Filed under: Άλυτα Προβλήματα — Themis Mitsis @ 3:52 μμ

Την άσκηση (η οποία οφείλεται στον Adolph Winkler Goodman) προτείνει ο Κ. Κουρουζίδης.

Έστω G ένα απλό γράφημα (χωρίς loops και περισσότερες από μια ακμές που να συνδέουν οποιεσδήποτε δύο κορυφές) με n κορυφές.
Έστω t(G) ο συνολικός αριθμός τριγώνων στο G και στο \overline G (το γράφημα που είναι το συμπλήρωμα του G) μαζί.
Αποδείξτε ότι: t(G)=\binom{n}{3}-(n-2)e(G)+\sum_{v\in V(G)}\binom{d(v)}{2},
όπου:
e(G) είναι το πλήθος των ακμών.
V(G) είναι το σύνολο των κορυφών του G.
v είναι η εκάστοτε κορυφή.
d(v) είναι ο βαθμός της εκάστοτε κορυφής.

 

Υπόδειξη: Αναλογιστείτε την συνεισφορά σε κάθε ακμή από κάθε τριάδα κορυφών.

 

Advertisements

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: