Φράγματα του μέγιστου αριθμού εμβυθίσεων γράφων

Περίληψη

Η Θεωρία Άκαμπτων Γράφων (Θ.Α.Γ.) είναι ο κλάδος των μαθηματικών που μελετά τις εμβυθίσεις γράφων (ή διαμορφώσεις) σε έναν ευκλείδιο χώρο ή μια πολλαπλότητα. Εφόσον ο αριθμός των εμβυθίσεων ως προς τις ευκλείδιες κινήσεις είναι πεπερασμένος για δεδομένα βάρη των ακμών του γράφου, που αντιστοιχούν σε αποστάσεις, τότε ο γράφος ονομάζεται άκαμπτος, αλλιώς ονομάζεται έυκαμπτος. Ο υπολογισμός του αριθμού αυτού μπορεί να γίνει συνδέοντας τις αποστάσεις μεταξύ κορυφών που βρίσκονται σε μία ακμή με αλγεβρικά συστήματα. Ως εκ τούτου ο αριθμός των πραγματικών ριζών αυτών των συστημάτων αντιστοιχεί στον αριθμό των διαμορφώσεων. Οι μιγαδικές ρίζες αυτών των συστημάτων επεκτείνουν την έννοια των άκαμπτων γράφων στους μιγαδικούς ευκλείδιους χώρους και τις αντίστοιχες πολλαπλότητες. Ένα από τα βασικά ερωτήματα στην Θ.Α.Γ. είναι η αναζήτηση άνω φραγμάτων στον αριθμό των εμβυθίσεων για έναν δοσμένο αριθμό κορυφών που να μπορούν να πραγματωθούν. Το μέχρι τώρα γνωστό άνω φράγμα για κάθε ευκλείδιο χώρο δι ...
περισσότερα

Περίληψη σε άλλη γλώσσα

Rigidity theory is the branch of mathematics that studies the embeddings (or equivalently realizations) of graphs in an euclidean space or a manifold.If the number of realizations satisfying edge length constraints is finite up to rigid motions, then the embedding is called rigid, otherwise it is called flexible. These embeddings can be related to the real solutions of certain algebraic systems and their complex solutions extend the notion of rigidity to $\mathbb{C}^d$. One of the major open problems in rigidity theory is to find tight upper bounds on the numbers of rigid graph realizations in an embedding space for a given number of vertices.Given a minimally rigid graph $G(V,E)$, the upper bound of embeddings in $\RR^d$ used to be $O\left(2^{d \cdot |V|}\right)$, while for the cases of $d=2$ and $d=3$ it has been proved that there are graphs with $\Omega\left(2.3003^{|V|}\right)$ and $\Omega\left(2.5198^{|V|}\right)$ realizations respectively. In this thesis, we display methods that ...
περισσότερα

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/52067
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/52067
ND
52067
Εναλλακτικός τίτλος
Bounds on the maximal number of graph embeddings
Συγγραφέας
Μπάρτζος, Ευάγγελος του Κωνσταντίνος
Ημερομηνία
2022
Ίδρυμα
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών (ΕΚΠΑ). Σχολή Θετικών Επιστημών. Τμήμα Πληροφορικής και Τηλεπικοινωνιών. Τομέας Θεωρητικής Πληροφορικής
Εξεταστική επιτροπή
Εμίρης Ιωάννης
Θεοχάρης Θεοχάρης
Busé Laurent
Ζησιμόπουλος Βασίλειος
Γιαννοπούλου Αρχοντία
Schicho Josef
Σκούτας Δημήτριος
Επιστημονικό πεδίο
Φυσικές ΕπιστήμεςΜαθηματικά ➨ Διακριτά μαθηματικά και Συνδυαστική
Φυσικές ΕπιστήμεςΜαθηματικά ➨ Υπολογιστικά μαθηματικά
Λέξεις-κλειδιά
Άκαμπτα γραφήματα
Χώρα
Ελλάδα
Γλώσσα
Αγγλικά
Άλλα στοιχεία
εικ., πιν., σχημ.
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.