69,179 research outputs found
Caos e simetrias em sistemas quanticos
No full textDissertação (mestrado) - Universidade Federal de Santa Catarina. Centro de Ciencias Fisicas e MatematicasNeste trabalho são investigadas algumas propriedades espectrais de dois sistemas quânticos não separáveis: o hamiltoniano de Henon-Heiles e o oscilador harmônico bidimensional com perturbação sugerida por Pullen e Edmonds do tipo x2y2. Foi confirmado que estes sistemas apresentam uma transição do comportamento quântico regular para o comportamento quântico irregular, também chamado caótico, através do estudo da sensibilidade dos níveis a pequenas mudanças na perturbação. Estes resultados foram obtidos com melhor precisão do que os já publicados na literatura. Tanto na obtenção do espectro de energias quanto na própria análise da sensibilidade, a utilização dos grupos de simetrias destes sistemas quânticos foi muito importante. Assim, este trabalho contém um estudo detalhado das simetrias de sistemas quânticos em geral e sua aplicação no estudo dos hamiltonianos citados
On matrices with the Edmonds-Johnson property
No full textThe strong Chvátal rank of a rational matrix A is the smallest number t such that the polyhedron defined by the system b <= A x <= c, l <= x <= u has Chvátal rank at most t for all integral vectors b,c,l,u. Matrices with strong Chvátal rank at most 1 are said to have the Edmonds-Johnson property. There are two main classes of matrices known to have the Edmonds-Johnson property, one was introduced by Edmonds and Johnson, and the other by Gerards and Schrijver.
Characterizing integral matrices with the Edmonds-Johnson property seems complicated. However, Gerards and Schrijver noticed that there are some openings if we restrict ourselves to totally half-modular matrices, and they conjectured a characterization of totally half-modular matrices with the Edmonds-Johnson property. In this thesis we introduce two new classes of totally half-modular matrices with the Edmonds-Johnson property, that prove the validity of the conjecture by Gerards and Schrijver in two particular cases.
In Chapter 3 we study systems of the from b <= Mx <= d, l <= x <= u, where M is obtained from a totally unimodular matrix with two nonzero elements per row by multiplying by 2 some of its columns, and b,d,l,u are integral vectors. We give an explicit description of a totally dual integral system that describes the integer hull of the polyhedron P defined by the above inequalities. Since the inequalities of such totally dual integral system are Chvátal inequalities for P, our result implies that the matrix M has the Edmonds-Johnson property.
In Chapter 4 we consider the class of totally half-modular matrices obtained from matrices 0, ± 1 with at most two nonzero entries per column by multiplying by 2 some of the columns. In this class we characterize, in terms of excluded minors, the matrices that have the Edmonds-Johnson property.Il rango forte di Chvátal di una matrice razionale A è il più piccolo numero t tale che il poliedro definito dal sistema b <= A x <= c, l <= x <= u ha rango di Chvátal al più t per tutti i vettori interi b,c,l,u. Matrici con rango forte di Chvátal al più 1 si dicono avere la proprietà di Edmonds-Johnson. Ci sono due principali classi note di matrici con la proprietà di Edmonds-Johnson, una fu introdotta da Edmonds e Johnson, e l'altra da Gerards e Schrijver.
Caratterizzare le matrici intere con la proprietà di Edmonds-Johnson sembra complicato. Tuttavia, Gerards e Schrijver notarono che ci sono più possibilità se ci restringiamo alle matrici totalmente 1/2-modulari, e congetturarono una caratterizzazione delle matrici totalmente 1/2-modulari con la proprietà di Edmonds-Johnson. In questa tesi introduciamo due nuovi classi di matrici totalmente 1/2-modulari con la proprietà di Edmonds-Johnson, che provano la validità della congettura di Gerards e Schrijver in due casi particolari.
Nel Capitolo 3 studiamo sistemi nella forma b <= Mx <= d, l <= x <= u, dove M è ottenuta da una matrice totalmente unimodulare con due elementi diversi da zero per riga moltiplicando per 2 alcune colonne, e b,d,l,u sono vettori interi. Noi diamo una descrizione esplicita di un sistema totally dual integral che descrive l'inviluppo convesso dei punti interi del poliedro P definito dalle disuguaglianze precedenti. Dato che le disuguaglianze di tale sistema totally dual integral sono disuguaglianze di Chvátal per P, questo implica che la matrice M ha la proprietà di Edmonds-Johnson.
Nel Capitolo 4 consideriamo la classe delle matrici totalmente 1/2-modulari ottenute da matrici 0, ± 1 con al più due elementi non zero per colonna moltiplicando per 2 alcune colonne. In questa classe caratterizziamo, in termini di minori esclusi, le matrici che hanno la proprietà di Edmonds-Johnson
Penentuan Matching Maksimum pada Graf menggunakan Algoritma Matching Edmonds
No full textMatching M pada graf G = (V, E) adalah himpunan sisi sedemikian sehingga tidak terdapat dua sisi di M yang bertemu pada titik yang sama. Suatu matching dikatakan maksimum di G jika dan hanya jika tidak terdapat lintasan augmenting pada graf G. Salah satu algoritma yang digunakan dalam mencari matching maksimum pada graf yaitu algoritma matching Edmonds. Penelitian ini membahas tentang proses pencarian matching maksimum pada graf bipartit lengkap K6,6 dan graf piramida Pr3 dengan algoritma matching Edmonds. Berdasarkan hasil penelitian, diperoleh matching maksimum pada graf bipartit lengkap (K6,6, M) yang mempunyai kardinalitas M'=6 dan matching maksimum pada graf piramida (Pr3, M) yang mempunyai kardinalitas M'=5
- …
