[Διακριτά Μαθηματικά] Παλιά θέματα - Σχολιασμός και απορίες

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[Admins]

Για αλλαγή του public name σας, επικοινωνήστε με έναν από τους Admins.

[Guybrush]

Στα θέματα Ιουνίου 2009:
(2)
(α) Δείξτε ότι έαν ένα απλό γράφημα έχει κύκλο Hamilton, τότε δεν μπορεί να περιέχει γέφυρα.
Ισχύει αυτό εάν έχει κύκλο Euler?
(β) Δείξτε ότι το συμπληρωματικό κάθε απλού μη συνδεόμενου γραφήματος είναι συνδεόμενο.

Καμία ιδέα;

(α) Είναι τόσο απλό όσο το σκέφτομαι; Εφόσον έχει γέφυρα, δεν μπορώ να επιστρέψω στην αρχική κορυφή χωρίς να διασχίσω και πάλι τη γέφυρα;
(β)"συνδεόμενο" means?

[^^DaRk_HunTeR]

Ναι ειναι τοσο απλο... βγαινει απο τον ορισμο του κυκλου euler και του κυκλου Hamilton.
 
Συνδεομενο η Συνεκτικο ονομαζεται ενα μη κατευ8υνομενο γραφημα αν υπαρχει μονοπατι μεταξυ καθε δυο κορυφων(σελ 180 βιβλιο)

γενικα τα θεματα ηταν τρομακτικα εκ 1ης οψεως, αλλα βγαιναν ολα απο τους ορισμους των εννοιων,με λιγα λογια γραψαμε εκ8εσεις

[Guybrush]

Για Euler ισχύει ή όχι;

[^^DaRk_HunTeR]

ναι προφανως an Eulerian path is a path in a graph which visits each edge exactly once
δεν μπορει να περιεχει γεφυρα γιατι θα περασει δυο φορες απο τις κορυφες που αποτελουν τη "γεφυρα".

[Guybrush]

ευχαριστώ πολύ Dark

[glika]

μπορεί κάποιος να πει πως λυνόταν το 2β και 3β των θεμάτων ιουνίου??

[BabylonX]

Έχω 2 λύσεις στο μυαλό μου για το 1)β του Ιουνη 2009 αλλά δε μπορώ να φανταστώ ποιά είναι η σωστή!

Α λύση.
Από το α έχουμε βρεί ότι οι πιθανές μεταθέσεις με 16 φορές επανάλληψη του Ο είναι 20!/16!=116280
Εάν θεωρήσουμε 2 Ο σταθερά στην αρχή και στο τέλος θα έχουμε ενδιάμεσα το ίδιο πρόβλημα με πρίν μόνο που έχουμε 18 θέσεις με 14 επαναλήψεις του Ο δηλαδή 18!/14!=73440 μεταθέσεις. Εάν αφαιρέσουμε αυτές από όλες τις δυνατές μεταθέσεις έχουμε 116280-73440=42840 πιθανές μεταθέσεις.

Β λύση.
Αν θεωρήσουμε ότι έχουμε ένα από τα Α,Β,Γ,Δ στην αρχή και ένα στο τέλος, οι πιθανές μεταθέσεις τους (Αρχή-Τελος) είναι 12 (Α-Β,Α-Γ,Α-Δ,Β-Α,Β-Γ,Β-Δ,Γ-Α,Γ-Β,Γ-Δ,Δ-Α,Δ-Β,Δ-Γ)
Για κάθε μία από αυτές θεωρούμε ότι ενδιάμεσα έχουμε τα υπόλοιπα δύο γράμματα από τα Α,Β,Γ,Δ που απομένουν και 16 Ο δηλαδή συνολικα 18 θέσεις. Οι πιθανές μεταθέσεις είναι 18!/16!=306. Δηλαδή έχουμε 306 μεταθέσεις στο εσωτερικό για κάθε μία από τις 12 μεταθέσεις των 2 γραμμάτων που βρίσκονται στα άκρα. Άρα 12*306=3672 μεταθέσεις.

Τελευταία φορά που έλεγξα, 42840≠3672. Που την κάνω τη μαλακία;

EDIT:
Εντάξει το βρήκα. Στην Α λύση είναι το λάθος καθώς δεν πρέπει να αφαιρέσω μόνο τις περιπτώσεις με Ο στην αρχή και στο τέλος. Πρέπει να αφαιρεθούν και οι περιπτώσει με Ο μόνο στην αρχή ή μόνο στο τέλος (2x) και όλες οι παραπάνω για κάθε ένα απο τα Α,Β,Γ,Δ (4x). Με λίγα λόγια, εκτός από τις 42840 μεταθέσεις για στάνταρ Ο στα άκρα πρέπει να αφαιρεθούν και οι (18!/15!)*2*4=39168 που αφορούν μόνο ένα Ο στην αρχή ή στο τέλος. Έτσι παίρνουμε και πάλι 3672 μεταθέσεις.

[+satyr]

μπορεί κάποιος να πει πως λυνόταν το 2β και 3β των θεμάτων ιουνίου??

Για το 2β δες το συνημμένο στην 6η σελίδα (κόκκινα γράμματα).

Για το 3β δεν ξέρω.
Επίσης αν μπορεί κάποιος να δώσει λύση στο θέμα 2 και 3 του Ιούνη 2008, και Σεπτέμβρη 2007 (χρωματικός αριθμός) plz!!!!

[Vicariously,I]

ναι γενικα οποιος μπορει να πει εστω και δυο λογια για το πως βγαινουν τα θεματα 2008 και 2009..

οσο για τον χρωματικο αριθμο ειδα ενα βιβλιο στην βιβλιοθηκη των ηλεκτρολογων που κατι λεει αλλα δεν το'χω διαβασει ακομα

[hatzf]

Ρε παιδια δεν ειπε ο Πιτσουλης οτι θα βαλει απο τις λυμενες ασηκσεις του ethmmy? Λαθος καταλαβα?

[zeus90]

Ναι ετσι είπε

[hatzf]

E τοτε γτ ¨κωλοτρωγονται¨ με τα παλια θεματα αφου ξερουν τα "θεματα¨"?

[sakaflias7]

ela mou nte

[saddodancererer]

ναι προφανως an Eulerian path is a path in a graph which visits each edge exactly once
δεν μπορει να περιεχει γεφυρα γιατι θα περασει δυο φορες απο τις κορυφες που αποτελουν τη "γεφυρα".

πιστευω οτι κανεις λαθος εδω.. δεν μας πειραζει δεν πα να περασει και 100 φορες απο μια κορυφη.. αφτο που μας ενοχλει ειναι να περασει πανω απο μια ακμη πανω απο 1 φορες.. οποτε μπορει να περιεχει eulerian path.. hamilton ομως δεν μπορει. δοκιμασε το με ενα απλο γραφο με γεφυρα

[saddodancererer]

και επισης το θεμα 1 ιουνιου 2008, αν και λυνεται με περιεργο τροπο στις σημειωσεις δεν μπορουμε να το λυσουμε και περνωντας τα 000 σαν ενα γραμμα?