forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 14 Δεκ 2018, 16:21

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 25 δημοσιεύσεις ]  Μετάβαση στην σελίδα 1, 2  Επόμενο
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Log Γραφημάτων
ΔημοσίευσηΔημοσιεύτηκε: 29 Σεπ 2008, 19:58 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 23 Νοέμ 2006, 10:32
Δημοσ.: 1888
Δευτέρα, 19-09-08

Εισαγωγικά μαθήματος - Ιστορικά στοιχεία (πρόβλημα 4 χρωμάτων κτλ)
Ορισμός του γράφου (περιγραφικός και αυστηρός)
Είδη γράφων (συνεκτικός, απλός κτλ)
Ορισμοί (Συμπληρωματικός γράφος, Διμερές γράφημα, δρόμος κα)
Αρχή του Περιστερώνα
Η έννοια του δέντρου
Θεωρήματα
---------------------------------------------------------------------------------------------

Την τρίτη ώρα (11-12) δεν μπορούσα να παρακολουθήσω οπότε δεν γνωρίζω τι ακριβός έκανε (τα θεωρήματα που λέω παραπάνω :D - μια σειρά θεωρημάτων πάνω στα δέντρα νομίζω είχε πει πριν το διάλυμα ότι θα ήταν.)
Όποιος μπορεί και έχει χρόνο ας συνεισφέρει σε αυτό το log. Γενικά τα log μαθήματος (που πρωτοξεκίνησαν πέρσι νομίζω) πιστεύω ότι είναι πολύ χρήσιμα για τα παιδιά που δεν μπορούν να παρακολουθούν. Ελπίζω να γίνει και φέτος σε όσα περισσότερα μαθήματα γίνεται.

Όσο για το μάθημα επίσης, μάλλον τη Δευτέρα θα γίνεται 9-11, ενώ θα προστεθεί άλλη μία ώρα μάλλον την παρασκευή (θα βγουν ανακοινώσεις). Επίσης μάλλον θα υπάρξει μια υπολογιστική προαιρετική εργασία, για όσους θέλουν να υλοποιήσουν κάποια πράγματα σε γλώσσα προγραμματισμού.

_________________
"Πριν ξεκινήσουμε να συζητάμε, πρέπει πρώτα να ορίζουμε τις έννοιες για να μπορέσουμε να συνεννοηθούμε" - Σωκράτης


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 30 Σεπ 2008, 06:55 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 07 Μαρ 2007, 17:47
Δημοσ.: 392
Τοποθεσια: Gothenburg, Sweden
Να συμπληρώσω ότι την 3η ώρα δεν έγινε μάθημα αφού οι περισσότεροι είχαν φύγει για τα υποχρεωτικά, και ήθελε να τα παραδώσει σε όλους, οπότε απλά είπε ότι Δευτέρα θα γίνεται σίγουρα 9-11, και αναμένουμε ανακοίνωση για την Παρασκευή με τον κ.Καρτσακλή.

Πολύ σωστή η ιδέα του log θα προσπαθήσω να βοηθάω όπου μπορώ.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 04 Οκτ 2008, 10:13 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 02 Οκτ 2006, 21:24
Δημοσ.: 495
Παιδιά θα γίνονται ασκήσεις και εφαρμογές από τον κύριο Καρτσακλή κάθε Τρίτη 14:00 με 15:00 εκτός του τρίωρου που υπάρχει την Δευτέρα

_________________
The good thing with mathematics is that you cannot stop playing with the numbers… the bad thing with mathematics is that you cannot stop playing with numbers… :)


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 04 Οκτ 2008, 10:17 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 11 Ιούλ 2007, 23:20
Δημοσ.: 360
pad3lws1989 έγραψε:
εκτός του τρίωρου που υπάρχει την Δευτέρα


δίωρο είναι την δευτερα 9 με 11


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 04 Οκτ 2008, 10:20 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 02 Οκτ 2006, 21:24
Δημοσ.: 495
Παράθεση:
δίωρο είναι την δευτερα 9 με 11


το πρόγραμμα γράφει για τρίωρο αν θυμάμαι καλά. Η αλήθεια είναι ότι και εγώ για δύωρο έχω ακούσει αλλά λέω τι λέει το πρόγραμμα...

_________________
The good thing with mathematics is that you cannot stop playing with the numbers… the bad thing with mathematics is that you cannot stop playing with numbers… :)


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 04 Οκτ 2008, 10:29 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 23 Νοέμ 2007, 21:39
Δημοσ.: 130
Τοποθεσια: ΝΙΚΑΙΑ
Δίωρο είναι την Δευτέρα 9-11 με τον κ. Σπύρου. Αλλά η άλλη ώρα με τον κ. Καρτσακλή δεν είναι γνωστό πότε θα γίνεται. Είπε πως θα βγάλει ανακοίνωση.

_________________
Ανάθεμα το θέαμα στην Κόλαση της Δύσης,
που κάνει ανταλλακτική κάθε αξία χρήσης


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 04 Οκτ 2008, 11:19 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 11 Ιούλ 2007, 23:20
Δημοσ.: 360
DIONISIS2 έγραψε:
Δίωρο είναι την Δευτέρα 9-11 με τον κ. Σπύρου. Αλλά η άλλη ώρα με τον κ. Καρτσακλή δεν είναι γνωστό πότε θα γίνεται. Είπε πως θα βγάλει ανακοίνωση.


Νιονιο μου είπε ο σπύρου την τρίτη θα κάνουμε την άλλη ώρα


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 05 Οκτ 2008, 18:13 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 15 Φεβ 2008, 16:00
Δημοσ.: 148
Με τον κ.Καρτσακλη θα έχουμε Τρίτη 2-3


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 06 Οκτ 2008, 10:59 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 23 Νοέμ 2006, 10:32
Δημοσ.: 1888
Δευτέρα, 06-10-08 (2ο μάθημα θεωρίας)

Ισόμορφοι γράφοι (παραδείγματα)
Δομή του δέντρου - βασικά θεωρήματα:
Πρόταση 1: Ένα γραφημα που έχει το πολύ 2ν κορυφές και βαθμό κορυφών ν, είναι συνεκτικό.
Πρόταση 2: Ένα συνεκτικό γράφημα (με τουλάχιστον 2 κορυφές) έχει ακμές λιγότερες από τις κορυφές του. Τότε έχει κορυφή βαθμού 1.
Πρόταση 3: Ένα συνακτικό γράφημα με ν κορυφές έχει τουλάχιστον ν-1 ακμές (απόδειξη με επαγωγή)
Ελάχιστός αριθμός ακμών συνεκτικού γραφήματος: ν-1
Μέγιστος αριθμός ακμών συνεκτικού γραφήματος: ν(ν-1)/2
Ορισμός: Δέντρο είναι ένα συνεκτικό γράφημα το οποίο δεν έχει κύκλο
Πρόταση 4: Σε συνεκτικό γράφημα με κύκλο, αν αφαιρέσω ακμή του κύκλου, το γράφημα παραμένει συνεκτικό.
Πρόταση 5: Τα συνεκτικά γραφήματα με ν κορυφές και ν-1 ακμές είναι δέντρα.
Πρόταση 6: Γράφημα με ν (ν\geq3) κορυφές και ν ακμές περιέχει κύκλο (απόδειξη με επαγωγή)
Πρόταση 7: Ένα δέντρο με ν κορυφές έχει ν-1 ακμές/
Τα παρακάτω είναι ισοδύναμα:
- Γ δέντρο
- Γ ελάχιστα συνεκτικό
- Γ μέγιστο άκυκλο (αν πάρει άλλη μία ακμή->κύκλος)
Πρόβλημα ελάχιστου κόστους (παράδειγμα που υπάρχει και στο βιβλίο)
Εύρεση βέλτιστου αλγορίθμου (πάμε στη μέγιστη ακμή. Αν ανήκει σε κύκλο, την αφειρούμε). Απόδειξη.

------------------------------------------------------------------------------------------------
Λογικά και χάρη στον GS και τις σημειώσεις του, δεν χρειάζεται πιά log... Θα το συνεχίσω όμως λίγο ακόμα και βλέπουμε.
Το log θα αφορά μόνο τη θεωρία καθώς στις ασκήσεις της Τρίτης δεν θα μπορώ να πηγαίνω. Ελπίζω να πηγαίνει ο φίλος μας ο GS και να ανεβάζει και τις σημειώσεις από τις ασκήσεις. Διαφορετικά αν μπορεί κάποιος ας ενημερώνει αυτό log για το τι ασκήσεις πάνω κάτω γίναν κάθε Τρίτη. :)

_________________
"Πριν ξεκινήσουμε να συζητάμε, πρέπει πρώτα να ορίζουμε τις έννοιες για να μπορέσουμε να συνεννοηθούμε" - Σωκράτης


Τελευταία επεξεργασία απο eliascm21 την 17 Οκτ 2008, 13:24, επεξεργάστηκε 1 φορές συνολικά.

Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 17 Οκτ 2008, 13:23 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 23 Νοέμ 2006, 10:32
Δημοσ.: 1888
Δευτέρα, 13-10-08 (3o μάθημα θεωρίας)

Δέντρα
P_1 το πλήθος κορυφών βαθμού 1
λ το πλήθος κορυφών βαθμού >2
Τότε, P_1 \geq \lambda +2. Απόδειξη...
κ-συνεκτικό δέντρο. Ισχύει σκ(Γ) \leq σα(Γ) \leq δ(Γ) (σκ(Γ), σα(Γ), δ(Γ) συνεκτικότητα κορυφών, συνεκτικότητα ακμών και ο μικρότερος βαθμος αντίστοιχα)
Ασκήσεις (υπάρχουν στο βιβλίο):
- Πόσα απλά και συνεκτικά γραφήματα με 8 κορυφές και βαθμό κορυφής τουλάχιστον 3 μπορώ να γράψω?
- Πόσα απλά μη συνεκτικά, με 15 ακμές και 7 κορυφές?
Ένα γράφημα είναι 2-συνεκτικό αν και μόνο αν για κάθε 2 κορυφές υπάρχει κύκλος που τις συνδέει. Απόδειξη...
Θεώρημα του Euler.

_________________
"Πριν ξεκινήσουμε να συζητάμε, πρέπει πρώτα να ορίζουμε τις έννοιες για να μπορέσουμε να συνεννοηθούμε" - Σωκράτης


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re:
ΔημοσίευσηΔημοσιεύτηκε: 21 Οκτ 2008, 22:52 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 15 Φεβ 2008, 16:00
Δημοσ.: 148
eliascm21 έγραψε:

Λογικά και χάρη στον GS και τις σημειώσεις του, δεν χρειάζεται πιά log... Θα το συνεχίσω όμως λίγο ακόμα και βλέπουμε.
Το log θα αφορά μόνο τη θεωρία καθώς στις ασκήσεις της Τρίτης δεν θα μπορώ να πηγαίνω. Ελπίζω να πηγαίνει ο φίλος μας ο GS και να ανεβάζει και τις σημειώσεις από τις ασκήσεις. Διαφορετικά αν μπορεί κάποιος ας ενημερώνει αυτό log για το τι ασκήσεις πάνω κάτω γίναν κάθε Τρίτη. :)


Νομίζω θα ήταν καλό να συνεχίσεις γιατί το μάθημα το κάνει αρκετά προφορικά και για αυτό θα μπορούσε κάτι να μου ξεφύγει.
Με την ευκαιρία να πω μερικά θεωρήματα, προτάσεις ή ορισμούς κτλ επειδή τα λέει γρήγορα και δεν τον προλαβαίνω τα σημειώνω και μετά τα μεταφέρω από το βιβλίο.
Ευχαριστούμε για τον κόπο που καταβάλλεις!
Τις ασκήσεις της Τρίτης θα τις ανεβάζω εγώ. :wink:


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Log Γραφημάτων
ΔημοσίευσηΔημοσιεύτηκε: 22 Οκτ 2008, 18:39 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 23 Νοέμ 2006, 10:32
Δημοσ.: 1888
Δευτέρα, 20-10-08 (4o μάθημα θεωρίας)

Θεώρημα 3.2.2, σελίδα 52
Ας θεωρήσουμε ένα γράφημα Γ με ν\geq3. Αν για κάθε ζεύγος μη γειτονικών κορυφών x και ψ, με x\neqψ, έχουμε ότι το άθροισμα των βαθμών των κορυφών αυτών είναι τουλάχιστον ν, τότε υπάρχει κύκλος του Hamilton στο Γ.
Απόδειξη...
Άσκηση 3, σελίδα 55
Δείξατε ότι το γράφημα του Tutte στο σχήμα 3.6(b), δεν έχει κύκλο του Χάμιλτον.
Συστολή, σελίδα 29
Θεώρημα 2.2.2, σελίδα 30
Έστωσαν συνεκτικό γράφημα Γ και μία ακμή του α τα άκρα της οποίας αποτελούνται από διαφορετικές κορυφές. Τότε π(Γ)=π(Γ-{α})+π(Γ.α)
Απόδειξη...
Θεώρημα 2.2.3, σελίδα 31
Ο αριθμός των απλών ετικετταρισμένων γραφημάτων με ν κορυφές είναι 2^{n(n-1)/2}
Θεώρημα 2.2.4, σελίδα 32
Υπάρχουν n^{2-n} ετικετταρισμένα δέντρα με ν κορυφές (ν\geq2)
Απόδειξη...
Ελάχιστο κόστος διαδρομής, σελίδες 34-36
Άσκηση 10, σελίδα 57
Να δειχθεί ότι το γράφημα στο Σχήμα 3.8 δεν έχει δρόμο του Hamilton.
Κεφάλαιο 4
Σύζευξη - αρχικά
Θεώρημα του Hall (εφαρμογή 1 σελ. 60)

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

_________________
"Πριν ξεκινήσουμε να συζητάμε, πρέπει πρώτα να ορίζουμε τις έννοιες για να μπορέσουμε να συνεννοηθούμε" - Σωκράτης


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Log Γραφημάτων
ΔημοσίευσηΔημοσιεύτηκε: 22 Οκτ 2008, 20:06 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 19 Ιαν 2008, 03:43
Δημοσ.: 128
αυτη την τριτη 21-10 εγινε η ωρα του κ.καρτσακλη??


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Log Γραφημάτων
ΔημοσίευσηΔημοσιεύτηκε: 22 Οκτ 2008, 23:15 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 23 Νοέμ 2006, 10:32
Δημοσ.: 1888
myrto έγραψε:
αυτη την τριτη 21-10 εγινε η ωρα του κ.καρτσακλη??

Όχι σύμφωνα με τον GS εδώ
Αλλά ας γράφουμε τις απορίες σε άλλο topic καλήτερα, ώστε να μένουν εδώ συγκεντρωμένα τα μαθήματα που γίνονται :)

_________________
"Πριν ξεκινήσουμε να συζητάμε, πρέπει πρώτα να ορίζουμε τις έννοιες για να μπορέσουμε να συνεννοηθούμε" - Σωκράτης


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Log Γραφημάτων
ΔημοσίευσηΔημοσιεύτηκε: 27 Οκτ 2008, 11:56 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφη: 23 Νοέμ 2006, 10:32
Δημοσ.: 1888
Δευτέρα, 27-10-08 (5o μάθημα θεωρίας)


Σύζευξη (κεφάλαιο 4)
Βασικά: Σελ. 59-60
Θεώρημα του Hall (θεώρημα 4.1.1) - απόδειξη
Θεώρημα του Tutte (θεώρημα 4.1.2) - απόδειξη

_________________
"Πριν ξεκινήσουμε να συζητάμε, πρέπει πρώτα να ορίζουμε τις έννοιες για να μπορέσουμε να συνεννοηθούμε" - Σωκράτης


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 25 δημοσιεύσεις ]  Μετάβαση στην σελίδα 1, 2  Επόμενο

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group