Graph Sketching : Composants connectés

Dans cours

Description

Cette séance de cours couvre le concept de croquis graphique en mettant l'accent sur les composants connectés. Il examine diverses techniques pour esquisser des graphiques et identifier efficacement les composants connectés dans les modèles de streaming. L'instructeur explique le processus de flux de graphes dynamiques et d'ordre antagoniste dans les flux de graphes, en soulignant l'importance de maintenir la connectivité dans les flux d'insertion uniquement.

Connectez-vous pour regarder la vidéo

Source officielle

https://mediaspace.epfl.ch/media/0_oih5z0tk

À 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.

Séances de cours associées (488)

Concepts associés (119)

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.

Graphe orienté acyclique

En théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit. On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt). Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre partielle.

Lexique de la théorie des graphes

NOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.

Vertex cover

In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations.

SpaceX

vignette|Photo d'entreprise de quelques employés de SpaceX (23 février 2015). SpaceX, officiellement Space Exploration Technologies Corporation, est une entreprise américaine spécialisée dans le domaine de l'astronautique et du vol spatial. Fondée le 6 mai 2002 par Elon Musk, SpaceX est l'un des deux prestataires privés à qui la National Aeronautics and Space Administration (NASA) a confié un contrat de transport de fret vers la Station spatiale internationale (ISS) dans le cadre du programme COTS.