υπέρκύβος

1.  Να δειχθεί με επαγωγή ότι ο υπερκύβος n-διαστάσεων Qn
έχει n2
n-1
ακμές.
2.  Να δειχθεί με επαγωγή ότι ο υπερκύβος  n-διαστάσεων  Qn
έχει κύκλο  Hamilton


3.  Να δειχθεί με επαγωγή ότι ο υπερκύβος  n-διαστάσεων  Qn

περιέχει ακριβώς




διαφορετικούς υποκύβους διάστασης k, k=1,...,n.

4.  Να δειχθεί ότι ο υπερκύβος n-διαστάσεων  Qn
μπορεί να παραχθεί ως το γινόμενο
γραφημάτων των υπερκύβων m και n-m διαστάσεων, δηλαδή Qn = Qm
x Qn-m
, για
1


----------------

Θα δείξουμε με επαγωγή ότι ο υπερκύβος n διαστάσεων Q_n έχει 2^n-1 ακμές

Βάση επαγωγής

Για n=1 ο υπέρκύβος εχει μια κορυφή και καμιά ακμη. Ελέγχουμε τον παραπάνω τύπο να διαπιστώσουμε εάν ισχύει, Ο τύπος ειναι

Q_n έχει 2^n-1ακμεςμε n=1 έχουμε Q₁ έχει 2^1-1=2⁰=1 ακμές και ισχύει.

Επαγωγική υπόθεση: Υποθέτουμε ότι ο υπερκύβος κ διαστάσεων Q_k έχει κ2^κ-1 ακμές

Επαγωγικό Βήμα: Θα δείξουμε ότι η σχέση ισχύει για n=κ+1 δηλαδή θα δείξουμε ότι υπερκυβος κ+1 διαστάσεων έχει 2^(κ+1)-1ακμές δηλαδή θα δείξω

Q_κ+1 έχει (κ+1) 2^κ ακμές

Περνούμε δυο αντίγραφα Qk με κ2^κ-1 ακμές

Ενώνουμε κάθε κορυφή του πρώτου αντιγράφου με του δευτέρου  με 2^κ ακμές επιπλέον (όσες και οι ακμές του υπερκυβου). Δηλαδή ενώνουμε τις κορυφές με την ιδία αρίθμηση.

Συνολικά οι ακμές θα είναι

Κ*2^κ-1+ κ*2^κ-1 + 2^κ = 2κ2^κ-1+ 2^κ  =κ *2^κ+ 2^κ  =

= 2^κ(κ*+1).

Δηλαδή το πλήθος των ακμών του Q_κ+1 έχει (κ+1) 2^κ ακμές.

2.

Θα δείξουμε με την μέθοδο της επαγωγής ότι ο κύβος n διαστάσεων έχει κύκλο Hamilton. Αρχικά πρέπει να αναφέρουμε ότι κύκλος Hamilton μπορεί να πραγματοποιηθεί για n≥2 γιατί το n=0 στην πραγματικότητα είναι ένα σημείο και δεν μπορούμε να έχουμε κύκλο Και για n=1 οι κορυφές v1 και v2 σχηματίζουν ευθύγραμμο τμήμα

Βάση επαγωγής

Για n=2 ο υπέρκύβος έχει κύκλο Hamilton που σχηματίζεται εάν διασχίσουμε  με την σειρά τις κορυφές v1 ,v2 ,v3 και v4

Επαγωγική υπόθεση: Υποθέτουμε ότι κύβους κ διαστάσεων έχει κύκλο Hamilton για n=k

Επαγωγικό Βήμα: Θα δείξουμε ότι κυβος κ+1 διαστάσεων έχει κύκλο Hamilton δηλαδή θα δείξουμε ότι   η πρόταση ισχύει για n=k+1.

Ο κύβος κ+1 διαστάσεων προκύπτει εάν προσθέσουμε στον κύβο κ διαστάσεων  τον εαυτό του, δηλαδή περνούμε δυο αντίγραφα του Q_k και τα προσθέτουμε. Από την επαγωγική υπόθεση γνωρίζουμε ότι ο Qk (υπερκυβος) έχει κύκλο Hamilton.

Για παράδειγμα και μονό για να δείξουμε  την υπόθεση έστω  ότι ο υπερκυβος  κ=2 (Ο υπερκυβος v1a, v2a, v3a, v4a) και με την προσθήκη του επιπλέων υπερκυβου (του v1β, v2β, v3β, v1a)  δηλαδή για το κ+1=3 το σχήμα μας θα είναι παρακάτω.   ο v_iα (όπου ι οι κορυφές του υπερκυβου μας ) έχει κύκλο Hamilton και ο v_iβπου προσθέτουμε το ίδιο. Παρατηρούμε ότι του ο κύκλος Hamilton σχηματίζεται από τις κόκκινες γραμμές . Αρχικά ο κύκλος σχηματίζεται από το πρώτο υπερκυβο via (v1a, v2a, v3a, v4a) και προσλάβουμε  να επιστέψουμε στην κορυφή v1a –από την ακμή z- από την v4β μεταβαίνουμε στον δεύτερο υπερκυβο και διανύουμε το κύκλο  Hamilton του viβ έπειτα ξανά επιστρέφουμε στην v1a σχηματίζοντας το κύκλο .

Το παραπάνω παράδειγμα αναφέρθηκε γα να καταλάβουμε με περισσότερη λεπτομέρεια το κύκλο Hamilton στον υπερκύβο.

Μπορούμε  να μετασχηματίσουμε το παραπάνω παράδειγμα  γενικά για όλους τους υπερκυβους μέγεθος n.

Σε είναι υπερυκυβο Qk που από την επαγωγική υπόθεση έχει κύκλο Hamilton. Προσθέτουμε έναν δεύτερο υπερκυβο Qk ώστε ο υπερκυβος που θα σχηματιστεί θα είναι Qk+1 και ενώνουμε τις αντιστιχεις κορυφες τους. Τοτε ο ο υπερκυβος Qk+1 που προκύπτει θα έχει κύκλο Hamilton. O κύκλος σχηματίζεται από τον ένα κύκλο του πρώτου υπερκυβου και πριν μεταβούμε στην αρχική κορυφή μεταβαίνουμε στον δεύτερο υπερκυβο (με μια  από τις ακμες που ενώσαμε τους δυο υπερκυβους ) και επαναλαμβάνουμε τον αντίστοιχο κύκλο και στο δεύτερο υπερκυβο  Τελειώνοντας μεταβαίνουμε στην κορυφή που ξεκινήσαμε  για να σχηματίσουμε κύκλο.

Δηλαδή για n≥2  o υπερκυβος Qn έχει κύκλο Hamilton.

3.

ΘΑ δείξουμε με επαγωγή ότι ο υπερκυβος n διαστάσεων περιέχει 2^n-k διαφορετικούς υποκυβους διάστασης κ, με κ=1.

Έχουμε ότι κ=1 αρά και η ελάχιστη τιμή του n θα είναι 1 . Άρα και η Βάση της επαγωγής θα είναι 1

Βάση επαγωγής (n=1)

Για n=1

v1

v2

 

έχουμε 1 υπερκυβο v1v2 δηλαδή αποτελείται από τον εαυτό του (δηλαδή το ερώτημα είναι πόσα γραφήματα v1v2 περιέχει ο υπερκαλός n1 και η απάντηση είναι πως μόνο 1 , ο εαυτός του). Ο τύπος είναι

2^n-k = 2^1-1 =1*2⁰=1*1=1 δηλαδή ισχύει.

Επαγωγική υπόθεση (=m): Υποθέτουμε ότι η πρόταση ισχύει n=p  δηλαδή ο υπερκυβο Qp περιέχει 2^p-k διάστασης κ με κ=1 έως p.

 Επαγωγικό Βήμα(n=p+1):Θα δείξουμε  ότι ο υπερκυβος του Q_p+1 2^p+1-k διάστασης  κ όπου κ=1, .. , p+1.

Θα ελέγξουμε για κ=p+1 ο τύπος γίνεται

            2^p+1-(p+1)=1*2⁰=1*1

Σωστά περιέχει μόνο τον εαυτό του δηλαδή p=k+1 περιέχει έναν υπερκβο και  ισχύει