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

Οκτώβριος 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

2 Σχόλια »

  1. Όταν έχουμε μια άσκηση τέτοιου είδους, φαντάζομαι πρώτο πράγμα που πρέπει να ελέγξει κανείς είναι ότι ο αριθμός των τριγώνων
    τ(G) είναι ο ίδιος σε ένα γράφο ανεξάρτητα αν διαλέξουμε αυτόν ή το συμπλήρωμά του. Είναι δύσκολο να το αιτιολογήσουμε;
    Οποιαδήποτε σχόλια ευπρόσδεκτα. Φαντάζομαι αυτό θα είχε κατά νου αυτός που επινόησε τον τύπο..

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Οκτώβριος 13, 2018 @ 10:55 μμ

  2. To +,-,+ παραπέμπει στην αρχή του εγκλεισμού-αποκλεισμού μάλλον.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Οκτώβριος 14, 2018 @ 6:59 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση /  Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

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