Cortes en grafos utilizando resultados de teoría espectral
"Dentro de la gran variedad de problemas que se encuentran en el ámbito de teoría de grafos, hay muchos para los cuales encontrar una solución exacta es muy difícil o imposible. Uno de estos problemas es el de partición de un grafo no dirigido en n vértices, dadas unas restricciones en el volum...
- Autores:
-
Perdomo Villegas, Santiago
- Tipo de recurso:
- Trabajo de grado de pregrado
- Fecha de publicación:
- 2018
- Institución:
- Universidad de los Andes
- Repositorio:
- Séneca: repositorio Uniandes
- Idioma:
- spa
- OAI Identifier:
- oai:repositorio.uniandes.edu.co:1992/39221
- Acceso en línea:
- http://hdl.handle.net/1992/39221
- Palabra clave:
- Teoría de grafos
Teoría espectral (Matemáticas)
Matrices (Matemáticas)
Grafos bipartitos
Matrices laplacianas
Matemáticas
- Rights
- openAccess
- License
- http://creativecommons.org/licenses/by-nc-sa/4.0/
| id |
UNIANDES2_3db3e8e9f149c2bcc49a3313dffd7b67 |
|---|---|
| oai_identifier_str |
oai:repositorio.uniandes.edu.co:1992/39221 |
| network_acronym_str |
UNIANDES2 |
| network_name_str |
Séneca: repositorio Uniandes |
| repository_id_str |
|
| dc.title.es_CO.fl_str_mv |
Cortes en grafos utilizando resultados de teoría espectral |
| title |
Cortes en grafos utilizando resultados de teoría espectral |
| spellingShingle |
Cortes en grafos utilizando resultados de teoría espectral Teoría de grafos Teoría espectral (Matemáticas) Matrices (Matemáticas) Grafos bipartitos Matrices laplacianas Matemáticas |
| title_short |
Cortes en grafos utilizando resultados de teoría espectral |
| title_full |
Cortes en grafos utilizando resultados de teoría espectral |
| title_fullStr |
Cortes en grafos utilizando resultados de teoría espectral |
| title_full_unstemmed |
Cortes en grafos utilizando resultados de teoría espectral |
| title_sort |
Cortes en grafos utilizando resultados de teoría espectral |
| dc.creator.fl_str_mv |
Perdomo Villegas, Santiago |
| dc.contributor.advisor.none.fl_str_mv |
Ould Khaoua, Ahmed |
| dc.contributor.author.none.fl_str_mv |
Perdomo Villegas, Santiago |
| dc.contributor.jury.none.fl_str_mv |
Velasco Gregory, Mauricio Fernando |
| dc.subject.keyword.es_CO.fl_str_mv |
Teoría de grafos Teoría espectral (Matemáticas) Matrices (Matemáticas) Grafos bipartitos Matrices laplacianas |
| topic |
Teoría de grafos Teoría espectral (Matemáticas) Matrices (Matemáticas) Grafos bipartitos Matrices laplacianas Matemáticas |
| dc.subject.themes.none.fl_str_mv |
Matemáticas |
| description |
"Dentro de la gran variedad de problemas que se encuentran en el ámbito de teoría de grafos, hay muchos para los cuales encontrar una solución exacta es muy difícil o imposible. Uno de estos problemas es el de partición de un grafo no dirigido en n vértices, dadas unas restricciones en el volumen de las particiones. En este, se desea separar el conjunto de vértices en dos grupos con los requerimientos de minimizar el tamaño del corte, en otras palabras, el número de arcos entre los grupos, y maximizar el volumen de los conjuntos. Pero, las soluciones algorítmicas para el problema de encontrar el corte óptimo, son muy costosas. Usando teoría espectral buscaremos un método que nos permita encontrar una solución aproximada a este problema. Con este fin se encontrará una relajación del problema de hallar el mejor corte en términos del cociente de Raleigh de la matriz Laplaciana. Luego se demostrará la desigualdad de Cheeger para grafos regulares, la cual nos da una relación no trivial entre el mejor corte y el segundo valor propio. En la siguiente parte del capítulo se adapta el resultado a grafos irregulares. Con esto se construirá un algoritmo que, dado un vector propio asociado al segundo valor propio más pequeño, tiene como salida un corte que cumple la desigualdad de Cheeger."--Tomado del Formato de Documento de Grado. |
| publishDate |
2018 |
| dc.date.issued.none.fl_str_mv |
2018 |
| dc.date.accessioned.none.fl_str_mv |
2020-06-10T16:06:41Z |
| dc.date.available.none.fl_str_mv |
2020-06-10T16:06:41Z |
| dc.type.spa.fl_str_mv |
Trabajo de grado - Pregrado |
| dc.type.coarversion.fl_str_mv |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| dc.type.driver.spa.fl_str_mv |
info:eu-repo/semantics/bachelorThesis |
| dc.type.coar.spa.fl_str_mv |
http://purl.org/coar/resource_type/c_7a1f |
| dc.type.content.spa.fl_str_mv |
Text |
| dc.type.redcol.spa.fl_str_mv |
http://purl.org/redcol/resource_type/TP |
| format |
http://purl.org/coar/resource_type/c_7a1f |
| dc.identifier.uri.none.fl_str_mv |
http://hdl.handle.net/1992/39221 |
| dc.identifier.pdf.none.fl_str_mv |
u821112.pdf |
| dc.identifier.instname.spa.fl_str_mv |
instname:Universidad de los Andes |
| dc.identifier.reponame.spa.fl_str_mv |
reponame:Repositorio Institucional Séneca |
| dc.identifier.repourl.spa.fl_str_mv |
repourl:https://repositorio.uniandes.edu.co/ |
| url |
http://hdl.handle.net/1992/39221 |
| identifier_str_mv |
u821112.pdf instname:Universidad de los Andes reponame:Repositorio Institucional Séneca repourl:https://repositorio.uniandes.edu.co/ |
| dc.language.iso.es_CO.fl_str_mv |
spa |
| language |
spa |
| dc.rights.uri.*.fl_str_mv |
http://creativecommons.org/licenses/by-nc-sa/4.0/ |
| dc.rights.accessrights.spa.fl_str_mv |
info:eu-repo/semantics/openAccess |
| dc.rights.coar.spa.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| rights_invalid_str_mv |
http://creativecommons.org/licenses/by-nc-sa/4.0/ http://purl.org/coar/access_right/c_abf2 |
| eu_rights_str_mv |
openAccess |
| dc.format.extent.es_CO.fl_str_mv |
46 hojas |
| dc.format.mimetype.es_CO.fl_str_mv |
application/pdf |
| dc.publisher.es_CO.fl_str_mv |
Universidad de los Andes |
| dc.publisher.program.es_CO.fl_str_mv |
Matemáticas |
| dc.publisher.faculty.es_CO.fl_str_mv |
Facultad de Ciencias |
| dc.publisher.department.es_CO.fl_str_mv |
Departamento de Matemáticas |
| dc.source.es_CO.fl_str_mv |
instname:Universidad de los Andes reponame:Repositorio Institucional Séneca |
| instname_str |
Universidad de los Andes |
| institution |
Universidad de los Andes |
| reponame_str |
Repositorio Institucional Séneca |
| collection |
Repositorio Institucional Séneca |
| bitstream.url.fl_str_mv |
https://repositorio.uniandes.edu.co/bitstreams/3188ef61-3cda-44aa-8963-90b8bdd1bc87/download https://repositorio.uniandes.edu.co/bitstreams/0f4ea1ae-c46e-4a31-bea2-31f88dbb98a4/download https://repositorio.uniandes.edu.co/bitstreams/648835cf-19ae-4032-aa02-640de80a2f20/download |
| bitstream.checksum.fl_str_mv |
0fc5f9bedb9c3427e157d2ef759af963 88650a385371d428a6a31ba967d4968d b70b66bb7823d918ff90da743b3484cd |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio institucional Séneca |
| repository.mail.fl_str_mv |
adminrepositorio@uniandes.edu.co |
| _version_ |
1812134017153105920 |
| spelling |
Al consultar y hacer uso de este recurso, está aceptando las condiciones de uso establecidas por los autores.http://creativecommons.org/licenses/by-nc-sa/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Ould Khaoua, Ahmed5d9794a0-3838-4ccd-bd7d-2534b6a3a4ca400Perdomo Villegas, Santiago82105ad3-c525-4d20-84fb-c0d2a7262650500Velasco Gregory, Mauricio Fernando2020-06-10T16:06:41Z2020-06-10T16:06:41Z2018http://hdl.handle.net/1992/39221u821112.pdfinstname:Universidad de los Andesreponame:Repositorio Institucional Sénecarepourl:https://repositorio.uniandes.edu.co/"Dentro de la gran variedad de problemas que se encuentran en el ámbito de teoría de grafos, hay muchos para los cuales encontrar una solución exacta es muy difícil o imposible. Uno de estos problemas es el de partición de un grafo no dirigido en n vértices, dadas unas restricciones en el volumen de las particiones. En este, se desea separar el conjunto de vértices en dos grupos con los requerimientos de minimizar el tamaño del corte, en otras palabras, el número de arcos entre los grupos, y maximizar el volumen de los conjuntos. Pero, las soluciones algorítmicas para el problema de encontrar el corte óptimo, son muy costosas. Usando teoría espectral buscaremos un método que nos permita encontrar una solución aproximada a este problema. Con este fin se encontrará una relajación del problema de hallar el mejor corte en términos del cociente de Raleigh de la matriz Laplaciana. Luego se demostrará la desigualdad de Cheeger para grafos regulares, la cual nos da una relación no trivial entre el mejor corte y el segundo valor propio. En la siguiente parte del capítulo se adapta el resultado a grafos irregulares. Con esto se construirá un algoritmo que, dado un vector propio asociado al segundo valor propio más pequeño, tiene como salida un corte que cumple la desigualdad de Cheeger."--Tomado del Formato de Documento de Grado."Within the great variety of problems in the field of graph theory, there are plenty for which finding an exact solution is very hard or impossible. An example of this problems is the partitioning of an undirected graph in n edges, given some restrictions in the volume of the resulting partitions. Here it is needed to divide the set of edges into two subsets with the requirements of minimizing the size of the cut, in other words the number of edges between the sets, and maximizing the volume of the resulting sets. But, the algorithmic solutions to find the best cut are very computationally expensive. So, using spectral graph theory, we will find a method that will allow us to find a cut that is close to the optimal solution. With this end, we will study a relaxation of the problem in terms of the Raleigh quotient of the Laplacian matrix of the graph. Then we will provide a proof of Cheeger's inequality for regular graphs, which gives us a nontrivial relation between the optimal cut and the second smallest eigenvalue. Following this we will see the generalization of this inequality for irregular graphs. Having all of this, an algorithm will be developed such that, given an eigenvector of the second smallest eigenvalue, we have as an output a cut that satisfies the restrains of Cheeger's inequality."--Tomado del Formato de Documento de Grado.MatemáticoPregrado46 hojasapplication/pdfspaUniversidad de los AndesMatemáticasFacultad de CienciasDepartamento de Matemáticasinstname:Universidad de los Andesreponame:Repositorio Institucional SénecaCortes en grafos utilizando resultados de teoría espectralTrabajo de grado - Pregradoinfo:eu-repo/semantics/bachelorThesishttp://purl.org/coar/resource_type/c_7a1fhttp://purl.org/coar/version/c_970fb48d4fbd8a85Texthttp://purl.org/redcol/resource_type/TPTeoría de grafosTeoría espectral (Matemáticas)Matrices (Matemáticas)Grafos bipartitosMatrices laplacianasMatemáticasPublicationORIGINALu821112.pdfapplication/pdf647335https://repositorio.uniandes.edu.co/bitstreams/3188ef61-3cda-44aa-8963-90b8bdd1bc87/download0fc5f9bedb9c3427e157d2ef759af963MD51THUMBNAILu821112.pdf.jpgu821112.pdf.jpgIM Thumbnailimage/jpeg3123https://repositorio.uniandes.edu.co/bitstreams/0f4ea1ae-c46e-4a31-bea2-31f88dbb98a4/download88650a385371d428a6a31ba967d4968dMD55TEXTu821112.pdf.txtu821112.pdf.txtExtracted texttext/plain69222https://repositorio.uniandes.edu.co/bitstreams/648835cf-19ae-4032-aa02-640de80a2f20/downloadb70b66bb7823d918ff90da743b3484cdMD541992/39221oai:repositorio.uniandes.edu.co:1992/392212023-10-10 18:47:45.45http://creativecommons.org/licenses/by-nc-sa/4.0/open.accesshttps://repositorio.uniandes.edu.coRepositorio institucional Sénecaadminrepositorio@uniandes.edu.co |