Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Graph
Search

fr|en

Se Connecter

Concept

Graphe dual

Résumé

En théorie des graphes, le graphe dual d'un graphe plongé dans une surface est défini à l'aide des composantes de son complémentaire, lesquelles sont reliées entre elles par les arêtes du graphe de départ. Cette notion généralise celle de dualité dans les polyèdres. Il faut noter qu'un même graphe abstrait peut avoir des graphes duaux non isomorphes en fonction du plongement choisi, même dans le cas de plongements dans le plan. Un graphe (plongé) isomorphe à son dual est dit autodual. Construction Étant donné un graphe plongé dans une surface connexe, chaque composante connexe (ou cellule) du complémentaire est munie d'un point définissant un sommet du graphe dual. Chaque arête du graphe initial définit une arête du graphe dual reliant les composantes du complémentaire qui la bordent. Les arêtes du graphe dual peuvent être plongées dans la surface de façon que chacune coupe uniquement l'arête correspondante du graphe initial, et en un seul point. Propriétés

Source officielle

https://fr.wikipedia.org/wiki/Graphe_dual

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (9)

Chargement

Afficher plus

Publications associées

Chargement

Personnes associées (1)

Personnes associées

Chargement

Unités associées (1)

Unités associées

Chargement

Concepts associés (30)

Concepts associés

Chargement

Cours associés (4)

This course is an introduction to the non-perturbative bootstrap approach to Conformal Field Theory and to the Gauge/Gravity duality, emphasizing the fruitful interplay between these two ideas.

We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpected (and sometimes paradoxical) properties for which no other methods of construction are known.

L'objectif de ce cours est d'apprendre à réaliser de manière rigoureuse et critique des analyses par éléments finis de problèmes concrets en mécanique des solides à l'aide d'un logiciel CAE moderne.

Afficher plus

Cours associés

Chargement

Séances de cours associées (6)

Afficher plus

Séances de cours associées

Chargement

Publications associées (9)

An Maxflow Algorithm for Directed Planar Graphs

Luca Furrer

2010

Chargement

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

b \in \Z^m

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem of finding an optimal solution for an integer program is known as integer programming. Integer programming is NP-hard in general, though several algorithms exist: Lenstra provided an algorithm that is polynomial if the dimension

n

is fixed. For variable dimension, the best known algorithm depends linearly on

n

, and exponentially on the number of equalities as well as the largest absolute value of an entry in the matrix

A

. The first part of this thesis considers integer programming for variable dimensions and sparse matrices. We measure the sparsity of a matrix by the tree-depth of the dual graph of

A

. A typical example for these integer programs are

N

-fold IPs, used for scheduling and social choice problems. We obtain the currently fastest fixed-parameter tractable algorithm with parameters tree-depth and the largest absolute value of the entries in

A

. The running time we achieve is near-linear in the dimension. With a slightly worse running time, we are able to show that

N

-fold integer programs of constant block size can be solved in strongly polynomial time. Assuming the exponential time hypothesis, we complement these results with a lower bound on the parameter dependency that almost matches the parameter dependency of the running time. As a consequence, we provide the currently strongest lower bound for

N

-fold integer programs. Another problem closely related to integer programming is the closest vector problem. A lattice is a discrete additive subgroup of

\R^n

. The closest vector problem (CVP) asks for a lattice point closest to a given target vector. An important tool for solving the closest vector problem is the Voronoi cell

\vc

of a lattice

\Lambda \subseteq \R^n

, which is the set of all points for which

0

is a closest lattice point. It is a polytope whose facets are induced by a set of lattice vectors, the Voronoi relevant vectors. A generic lattice has exponentially many Voronoi relevant vectors, leading to exponential space for certain CVP algorithms. In the second part of this thesis, we introduce the notion of a

c

-compact lattice basis

B \in \R^{n \times n}

that facilitates to represent the Voronoi relevant vectors with coefficients bounded by

c

. Such a basis allows to reduce the space requirement of Micciancio's & Voulgaris' algorithm for the closest vector problem from exponential to polynomial, while the running time becomes exponential in

c

. We show that for every lattice an

n^2

-compact basis exists, but there are lattices for which we cannot choose

c \in o (n)

. If the Voronoi cell is a zonotope, we can choose

c=1

, providing a single-exponential time and polynomial space algorithm for CVP, assuming a

1

-compact basis is known. Deciding whether a given lattice has a certain structure that helps to solve the closest vector problem more efficiently is a reappearing and non-trivial problem. The third part of this thesis is concerned with the specific structure of having an orthonormal basis. We show that this problem belongs to NP

\cap

co-NP. Moreover, it can be reduced to solving a single closest vector problem. We also show that if a separation oracle for the Voronoi cell is provided, CVP is solvable in polynomial time.

EPFL2020

Chargement

Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs

Carsten Moldenhauer

Springer2011

Chargement

Afficher plus

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

b \in \Z^m

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

n

is fixed. For variable dimension, the best known algorithm depends linearly on

n

, and exponentially on the number of equalities as well as the largest absolute value of an entry in the matrix

A

. The first part of this thesis considers integer programming for variable dimensions and sparse matrices. We measure the sparsity of a matrix by the tree-depth of the dual graph of

A

. A typical example for these integer programs are

N

A

. The running time we achieve is near-linear in the dimension. With a slightly worse running time, we are able to show that

N

N

-fold integer programs. Another problem closely related to integer programming is the closest vector problem. A lattice is a discrete additive subgroup of

\R^n

. The closest vector problem (CVP) asks for a lattice point closest to a given target vector. An important tool for solving the closest vector problem is the Voronoi cell

\vc

of a lattice

\Lambda \subseteq \R^n

, which is the set of all points for which

0

c

-compact lattice basis

B \in \R^{n \times n}

that facilitates to represent the Voronoi relevant vectors with coefficients bounded by

c

c

. We show that for every lattice an

n^2

-compact basis exists, but there are lattices for which we cannot choose

c \in o (n)

. If the Voronoi cell is a zonotope, we can choose

c=1

, providing a single-exponential time and polynomial space algorithm for CVP, assuming a

1

\cap

co-NP. Moreover, it can be reduced to solving a single closest vector problem. We also show that if a separation oracle for the Voronoi cell is provided, CVP is solvable in polynomial time.

EPFL2020