No description available.

O Problema dos K Menores Caminhos é uma generalização do Problema do Menor Caminho, em que desejamos encontrar os K caminhos de menor custo entre dois vértices de um grafo. Estudamos e implementamos algoritmos que resolvem esse problema em grafos dirigidos, com peso nos arcos e que permitem apenas caminhos sem repetição de vértices na resposta. Comparamos seus desempenhos utilizando grafos do 9th DIMACS Implementation Challenge. Identificamos os pontos fortes e fracos de cada algoritmo, e propusemos uma variante híbrida dos algoritmos de Feng e de Pascoal. Essa variante proposta obteve desempenho superior aos algoritmos base em alguns grafos, e resultado superior a pelo menos um deles na grande maioria dos testes. / The K-Shortest Path Problem is a generalization of the Shortest Path Problem, in which we must find the K paths between two vertices in a graph that have the lowest costs. We study some K-Shortest Path Problem algorithms applied to weighted directed graphs, allowing only paths with no repeated vertices. We compare empirically implementation of some algorithms, using instance graphs from the 9th DIMACS Implementation Challenge. We identify the strengths and weaknesses of each algorithm, and we propose a hybrid version of Feng\'s and Pascoal\'s algorithms. This proposed variant achieve better perfomance compared to both base algorithms in some graphs, and it is better than at least one of them in most cases.

This Master’s Thesis consists of description of current routing protocols and routers, basic principles of neural networks and their interpretation in connection with the use for routing in data networks and telecommunications networks. In the thesis I focused on neural networks, which use energetic functions to find solution stabled states and their use for data routing. I produced the application software to test and find suitable variables for each function. This application counts the shortest path and is able to change variables to reach the best solution of stabled state of neural network. These solutions are compared with other functions that are usually used in nowadays systems for data network routing.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第21397号 / 情博第683号 / 新制||情||118(附属図書館) / 京都大学大学院情報学研究科社会情報学専攻 / (主査)教授 吉川 正俊, 教授 黒田 知宏, 教授 守屋 和幸 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

No description available.

Seit 1983 begründet die Publikationsreihe "Graph Minors" von N. Robertson und P.D. Seymour im Wesentlichen die Minorentheorie mit mächtigen Hilfsmitteln wie der Baumzerlegung und weitreichenden Resultaten wie dem Minorensatz. Für gerichtete Graphen existiert allerdings noch keine einheitliche Minorentheorie und verschiedene Ansätze werden in dieser Arbeit systematisiert. Einige gerichtete Versionen der Baumzerlegung (gerichtete Baumzerlegung nach B. Reed, arboreale, D- und DAG-Zerlegung) werden unter einheitlichen Aspekten untersucht. Die D-Weite ist dabei besonders vielversprechend. Enge Verbindungen zu zwei gerichteten Räuber-und-Gendarmen-Spielen werden unter analogen Aspekten betrachtet und sind wichtige Hilfsmittel. Der zentrale Begriff des Minoren ist im Wesentlichen für ungerichtete Graphen definiert und eine gerichtete Version wirft einige Probleme auf, welche untersucht werden. In \"Directed Tree-Width\" schlugen T. Johnson, N. Robertson, P.D. Seymour und R. Thomas 2001 einen Kompromiss vor. Durch Einschränkung der möglichen Kontraktionen soll der gewonnen Minorenbegriff mit einigen fundamentalen Anforderungen vereinbar sein und trotzdem ein mächtiges Werkzeug darstellen. Dieser Ansatz wird mit einer Anforderungsliste systematisch verfolgt und schrittweise Einschränkungen betrachtet. Die gerichtete Version topologischer Minoren ist dabei besonders vielversprechend. Die Minorentheorie gerichteter Graphen wird auf reduzible Flussgraphen angewandt. Wesentliche Resultate sind Konstruktionen arborealer und D-Zerlegungen mit Weite <2, sowie Gegenbeispiele für die Beschränktheit der DAG-Weite. Analoge Resultate folgen für die jeweiligen gerichteten Räuber-und-Gendarmen-Spiele.

Seit 1983 begründet die Publikationsreihe "Graph Minors" von N. Robertson und P.D. Seymour im Wesentlichen die Minorentheorie mit mächtigen Hilfsmitteln wie der Baumzerlegung und weitreichenden Resultaten wie dem Minorensatz. Für gerichtete Graphen existiert allerdings noch keine einheitliche Minorentheorie und verschiedene Ansätze werden in dieser Arbeit systematisiert. Einige gerichtete Versionen der Baumzerlegung (gerichtete Baumzerlegung nach B. Reed, arboreale, D- und DAG-Zerlegung) werden unter einheitlichen Aspekten untersucht. Die D-Weite ist dabei besonders vielversprechend. Enge Verbindungen zu zwei gerichteten Räuber-und-Gendarmen-Spielen werden unter analogen Aspekten betrachtet und sind wichtige Hilfsmittel. Der zentrale Begriff des Minoren ist im Wesentlichen für ungerichtete Graphen definiert und eine gerichtete Version wirft einige Probleme auf, welche untersucht werden. In \"Directed Tree-Width\" schlugen T. Johnson, N. Robertson, P.D. Seymour und R. Thomas 2001 einen Kompromiss vor. Durch Einschränkung der möglichen Kontraktionen soll der gewonnen Minorenbegriff mit einigen fundamentalen Anforderungen vereinbar sein und trotzdem ein mächtiges Werkzeug darstellen. Dieser Ansatz wird mit einer Anforderungsliste systematisch verfolgt und schrittweise Einschränkungen betrachtet. Die gerichtete Version topologischer Minoren ist dabei besonders vielversprechend. Die Minorentheorie gerichteter Graphen wird auf reduzible Flussgraphen angewandt. Wesentliche Resultate sind Konstruktionen arborealer und D-Zerlegungen mit Weite <2, sowie Gegenbeispiele für die Beschränktheit der DAG-Weite. Analoge Resultate folgen für die jeweiligen gerichteten Räuber-und-Gendarmen-Spiele.:1 Einleitung 1.1 Grundbegriffe der Graphentheorie 1.2 Reduzibilität 2 Über Minoren von Graphen 2.1 Minoren von Graphen 2.2 Topologische Minoren von Graphen 2.3 Baumzerlegung und Baumweite tw(G) 2.4 Wegzerlegung und Wegbreite pw(G) 2.5 Räuber-und-Gendarmen-Spiele auf Graphen 2.6 Resultate und Anwendungen 3 Über Minoren von Digraphen 3.1 Übertragung der Minorenrelation auf Digraphen 3.2 Hindernisse bei der De?nition einer gerichteten Baumweite 3.3 Arboreale Weite dtw(D) 3.3.1 Arboreale Weite und Räuber-und-Gendarmen-Spiele 3.3.2 Resultate und Anwendungen 3.4 Gerichtete Baumweite dtwR(D) 3.5 D-Weite dw(D) 3.6 DAG-Weite dgw(D) 3.6.1 DAG-Weite und Räuber-und-Gendarmen-Spiele 3.6.2 Resultate und Anwendungen 3.7 Räuber-und-Gendarmen-Spiele auf Digraphen 3.8 Eingeschränkte Minorenrelation für Digraphen 3.8.1 Die Teilgraphenrelation für Digraphen 3.8.2 Die topologische Minorenrelation für Digraphen 3.8.3 Die Minorenrelation auf Digraphen nach JRST 3.8.4 Eingeschränkte Minorenrelationen 4 Verbindungen zwischen Reduzibilität und Minoren von Digraphen 4.1 Reduzibilität und initiale Wurzeldigraphen 4.2 Charakterisierung der Reduzibilität durch eingeschränkte Minoren 4.3 Resultate der Minorentheorie für reduzible initiale Wurzeldigraphen 5 Zusammenfassung und Ausblick Literaturverzeichnis Abbildungsverzeichnis

On considère le problème d’advection-diffusion stationnaire v(∇u, ∇v)+( β•∇u, v) = (f, v) et non stationnaire d/dt (u(t), v) + v(∇u, ∇v)+( β•∇u, v) = (g(t), v), ainsi que le problème d’advection (β•∇u, v) = (f, v) sur un domaine polygonal borné du plan. Le terme de diffusion est approché par des éléments de Crouzeix Raviart et le terme de convection par une méthode upwind sur des volumes barycentriques finis avec un maillage triangulaire. Pour le problème stationnaire d’advection-diffusion, la L²-stabilité (c’est-à-dire indépendante du coefficient de diffusion v) est démontrée pour la solution du problème approché obtenue par cette méthode d’éléments finis et de volumes finis. Pour cela une condition sur la géométrie doit être satisfaite. Des exemples de maillages sont donnés. Toujours avec cette condition géométrique sur le maillage, une inégalité de stabilité (où la discrétisation en temps n’est pas couplée à une condition sur la finesse du maillage) est obtenue pour le cas non-stationnaire. La discrétisation en temps y est faite par un schéma d’Euler implicite. Une majoration de l’erreur, proportionnelle au pas en temps et à la finesse du maillage, est ensuite proposée et exprimée explicitement en fonction des données du problème. Pour le problème d’advection, une approche utilisant la théorie des graphes est utilisée pour obtenir l’existence et l’unicité de la solution, ainsi que le résultat de stabilité. Comme pour la stabilité du problème d’advection-diffusion, une condition géométrique - qui est équivalente pour les points intérieurs du maillage à celle du problème d’advection-diffusion - est nécessaire. / We consider the stationary linear convection-diffusion equation v(∇u, ∇v)+( β•∇u, v) = (f, v), the time dependent d/dt (u(t), v) + v(∇u,∇v)+( β•∇u, v)= (g(t), v) equation and the linear advection equation (β•∇u, v) = (f, v) on a two dimensional bounded polygonal domain. The diffusion term is discretized by Crouzeix-Raviart piecewise linear finite elements, and the convection term by upwind barycentric finite volumes on a triangular grid. For the stationary convection-diffusion problem, L²-stability (i.e. independent of the diffusion coefficient v) is proven for the approximate solution obtained by this combined finite-element finite-volume method. This result holds if the underlying grid satisfies a condition that is fulfilled, for example, by some structured meshes. Using again this condition on the grid, stability is shown for the time dependent convection-diffusion equation (without any link between mesh size and time step). An implicit Euler approach is used for the time discretization. It is shown that the error associated with this scheme decays linearly with the mesh size and the time step. This result holds without any link between mesh size and time step. The dependence of the corresponding error bound on the diffusion coefficient is completely explicit. For the stationary advection equation, an approach using graph theory is used to obtain existence, uniqueness and stability. As in the stationary linear convection-diffusion equation, the underlying grid must satisfy some geometric condition. / Gegenstand der Arbeit ist die zweidimensionale stationäre Konvektion-Diffusionsgleichung v(∇u, ∇v)+( β•∇u, v) = (f, v), die zeitabhängige Konvektion-Diffusionsgleichung d/dt (u(t), v) + v(∇u,∇v)+( β•∇u, v)= (g(t), v), sowie die Konvektionsgleichung (β•∇u, v) = (f, v). Der Diffusionsterm ist diskretisiert mittels Crouzeix-Raviart stückweise lineare Finite Elemente. Das Gebiet ist in Dreiecke unterteilt und der Konvektionsterm ist mittels einer upwind Methode auf Baryzentrische Finite Volumenelemente definiert. Für die stationäre Konvektion-Diffusionsgleichung, wird (d.h. von v unabhängige) L²-Stabilität der numerischen Lösung bewiesen. Voraussetzung dafür, ist die Erfüllung gewisser geometrischer Bedingungen an die Unterteilung des Gebiets. Beispiele von Unterteilungen die diese Bedingungen erfüllen, werden gegeben. Wieder an dieser geometrischen Bedingung geknüpft, wird Stabilität (d.h. die Zeitdiskretisierung ist entkoppelt von der Netzweite) für die zeitabhängige Konvektion-Diffusionsgleichung, bewiesen. Für die Zeitableitung wird dabei eine Implizite Euler Diskretisierung verwendet. Eine obere Schranke für den Diskretisierungsfehler, proportional zum Zeitdiskretisierungsparameter und zur Netzfeinheit, ausgedrückt als Funktion der Daten der Differenzialgleichung, wird gezeigt. Für die Konvektionsgleichung wird ein graphentheoretischer Zugang verwendet, der es ermöglicht Existenz, Eindeutigkeit und Stabilität, zu bekommen. Für die Stabilität, werden ähnliche geometrische Bedingungen an die Unterteilung des Gebiets gestellt, wie beim stationären Konvektion-Diffusionsproblem.

This Master Thesis deals with the drawing algorithms of graphs known from the mathematical theory. These algorithms deals with an appropriate distribution of the graph vertices in order to obtain the most clear and readable graphs for human readers. The main objective of this work was also to implement the drawing algorithm in the application that would allow to edit the graph. This work deals also with graphs representation in computers.