Séance de cours

Découpe la plus rapide: Algorithme de Leighton-Rao

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

CS-455: Topics in theoretical computer science

The students gain an in-depth knowledge of several current and emerging areas of theoretical computer science. The course familiarizes them with advanced techniques, and develops an understanding of fundamental questions that underlie some of the key probl ...

Description

Cette séance de cours couvre l'algorithme de Leighton-Rao pour trouver la coupe la plus clairsemée dans un graphique, en se concentrant sur les étapes de l'algorithme et les fondements théoriques. Il explique le processus d'identification de la coupe la plus clairsemée à l'aide d'ensembles de sommets et d'extensions de bords, avec une analyse détaillée des performances et des applications de l'algorithme.

Source officielle

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Concepts associés (32)

Théorie des graphes

vignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs.

Sommet (théorie des graphes)

vignette|Dans ce graphe, les sommets 4 et 5 sont voisins alors que les sommets 3 et 5 sont indépendants. Le degré du sommet 4 est égal à 3. Le sommet 6 est une feuille. En théorie des graphes, un sommet, aussi appelé nœud et plus rarement point, est l'unité fondamentale d'un graphe. Deux sommets sont voisins s'ils sont reliés par une arête. Deux sommets sont indépendants s'ils ne sont pas voisins. alt=A small example network with 8 vertices and 10 edges.|vignette|Réseau de huit sommets (dont un isolé) et 10 arêtes.

Mac OS 8

Mac OS 8 est le nom donné à la huitième révision majeure du système d'exploitation des ordinateurs Macintosh de la marque Apple. Pour la première fois il est nommé « Mac OS » (pour Macintosh Operating System), bien plus attrayant que les précédentes dénominations « Système » (ex. : Système 7). Apple ayant en effet décidé de rattraper les erreurs du Système 7 (à savoir : bugs à répétition avec les mises à jour 7.5, matériel non ou mal pris en charge, ...) en faisant disparaître tout ce qui avait trait à son prédécesseur.

Alphabet cyrillique

L’alphabet cyrillique est un alphabet permettant l'écriture de nombreuses langues d'Europe de l'Est et d'Asie centrale, principalement dans l'ex-URSS. Il est créé vers la fin du dans l'Empire bulgare, dans l'actuelle Bulgarie ou dans l'actuelle Macédoine du Nord, par des disciples du frère Cyrille ou peut-être Clément d'Ohrid (premier évêque de l'Église orthodoxe bulgare), à partir de l'alphabet grec dans sa graphie onciale et de l'alphabet glagolitique.

Proof (truth)

A proof is sufficient evidence or a sufficient argument for the truth of a proposition. The concept applies in a variety of disciplines, with both the nature of the evidence or justification and the criteria for sufficiency being area-dependent. In the area of oral and written communication such as conversation, dialog, rhetoric, etc., a proof is a persuasive perlocutionary speech act, which demonstrates the truth of a proposition.

Afficher plus

Séances de cours associées (64)

Convergence des Random Walks

Explore la convergence des marches aléatoires sur les graphiques et les propriétés des matrices de contiguïté pondérées.

Sparsest Cut: Théorie de l'ARV

Couvre la preuve du théorème ARV de Bourgain, en se concentrant sur lensemble fini de points dans un espace semi-métrique et lapplication de lalgorithme ARV pour trouver la coupe la plus clairsemée dans un graphique.

L'inégalité de Cheeger

Explore l'inégalité de Cheeger et ses implications dans la théorie des graphes.

Théorie des graphes spectraux : introduction

Introduit la théorie des graphes spectraux, explorant les valeurs propres et le rôle des vecteurs propres dans les propriétés des graphes.

Probabilité et statistiques

Couvre les moments, la variance et les valeurs attendues dans les probabilités et les statistiques, y compris la distribution des jetons dans un produit.

Afficher plus

Concepts associés (32)

Théorie des graphes

Sommet (théorie des graphes)