dir. (Universitat Autònoma de Barcelona. Departament d'Enginyeria de la Informació i de les Comunicacions)
| Additional title: |
Calculating the maximum flow in a network (directed graph) |
| Additional title: |
Càlcul del flux màxim en una xarxa (graf dirigit) |
| Date: |
2017-02-06 |
| Abstract: |
El presente proyecto de fin de grado esboza una solución informática al problema del flujo máximo, para lo cual se ha optado por utilizar el algoritmo de Ford-Fulkerson, al ser éste el más conocido y difundido, y que permite llegar a una solución exacta del problema en un tiempo relativamente corto. Dicho problema tiene una amplia gama de aplicaciones, que van desde cálculo de rutas disjuntas para redes de comunicaciones, circulación con capacidad, programación de líneas aéreas, selección de proyectos, entre otras. El problema del flujo máximo fundamentalmente consiste en: dada una red (o grafo) de arcos y nodos, cada arco con una capacidad determinada, y con un nodo fuente y otro destino, se trata de hallar la cantidad máxima de flujo que puede circular desde el nodo fuente hasta el nodo destino, de manera que el flujo individual que va por cada arco no supere la capacidad de sí mismo; esto último es conocido como restricción de capacidad del arco. Existe una vasta y variada cantidad de contextos que pueden modelarse como un problema de flujo máximo, las principales serán brevemente explicadas en la memoria descriptiva. |
| Abstract: |
The present project of end of degree outlines a computer solution to the problem of the maximum flow, for which it has chosen to use the algorithm of Ford-Fulkerson, being the one most known and diffused, and that allows to arrive to an exact solution of the problem in a relatively short time. This problem has a wide range of applications, ranging from calculation of disjoint routes for communications networks, capacity circulation, airline programming, project selection, among others. The problem of maximum flow basically consists of: given a network (or directed graph) of arcs and nodes, each arc with a determined capacity, and with a source node and target node, it is a matter of finding the maximum amount of flow that can flow from the source node to the destination node, so that the individual flow going through each arc does not exceed the capacity of itself; the last is known as the arc capacity constraint. There is a vast and varied number of contexts that can be modeled as a problem of maximum flow, the main ones will be briefly explained in this document. |
| Abstract: |
El present projecte de fi de grau esbossa una solució informàtica al problema del flux màxim, per al que s'ha aprofitat per utilitzar l'algoritme de Ford-Fulkerson, a l'est ser el més conegut i difós, i que permeten arribar a una solució exacta de l' problema en un temps relativament curt Dit problema té una àmplia gamma d'aplicacions, que va des del càlcul de rutes disyuntas per a xarxes de comunicacions, la capacitat de comunicació, la programació de línies aèries, la selecció de projectes, entre d'altres. El problema del flux màxim fonamentalment consisteix en: un vermell (o graf) d'arcs i de nodes, cada arc amb una capacitat determinada, i amb un node font i un altre destí, es tracta de la quantitat màxima de flux que pot circular des del node font fins al node destí, de manera que el flux individual que va per cada arc no superi la capacitat de si mateix; Això últim és conegut com a restricció de la capacitat de l'arc. Hi ha una vasta i variada quantitat de contextos que poden ser modelats com un problema de flux màxim, les principals són breument explicades en la memòria descriptiva. |
| Rights: |
Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial i la comunicació pública de l'obra, sempre que no sigui amb finalitats comercials, i sempre que es reconegui l'autoria de l'obra original. No es permet la creació d'obres derivades.  |
| Language: |
Castellà |
| Studies: |
Grau en Enginyeria Informàtica [2502441] |
| Study plan: |
Enginyeria Informàtica [958] |
| Document: |
Treball final de grau ; Text |
| Subject area: |
Menció Tecnologies de la Informació |
| Subject: |
Grafs ;
Flux màxim ;
Algoritme ford-fulkerson ;
Node origen ;
Node destí ;
Arcs ;
Capacitat ;
Aplicatiu ;
Java ;
TXT ;
Grafos ;
Flujo máximo ;
Algoritmo ford-fulkerson ;
Nodo origen ;
Nodo destino ;
Arcos ;
Capacidad ;
Aplicativo ;
Graphs ;
Max Flow ;
Algorithm ford-fulkerson ;
Source Node ;
Target Node ;
Capacity ;
Application |
guest ::
dir. (Universitat Autònoma de Barcelona. Departament d'Enginyeria de la Informació i de les Comunicacions)
