Logo
Unionpédia
Communication
Disponible sur Google Play
Nouveau! Téléchargez Unionpédia sur votre appareil Android™!
Gratuit
Accès plus rapide que le navigateur!
 

Isomorphisme de graphes

Indice Isomorphisme de graphes

En mathématiques, dans le cadre de la théorie des graphes, un isomorphisme de graphes est une bijection entre les sommets de deux graphes qui préserve les arêtes.

23 relations: Automorphisme de graphe, Équivalence logique, Bijection, Bijection réciproque, Complexité en temps, Cycle (théorie des graphes), Graphe griffe, Graphe orienté, Graphe triangle, Hassler Whitney, Hypergraphe, Isomorphisme, Line graph, Mathématiques, Morphisme de graphes, NP (complexité), Problème de l'isomorphisme de graphes, Problème NP-complet, Relation d'équivalence, Structure de données, Théorie de la complexité (informatique théorique), Théorie des graphes, Tracé de graphes.

Automorphisme de graphe

identité et la permutation qui échange les deux « murs » de la « maison ». En mathématiques et en particulier en théorie des graphes, un automorphisme de graphe est une bijection de l'ensemble des sommets vers lui-même qui préserve l'ensemble des arêtes.

Nouveau!!: Isomorphisme de graphes et Automorphisme de graphe · Voir plus »

Équivalence logique

En logique classique, deux propositions P et Q sont dites logiquement équivalentes ou simplement équivalentes quand il est possible de déduire Q à partir de P et de déduire P à partir de Q. En calcul des propositions, cela revient à dire que P et Q ont même valeur de vérité: P et Q sont soit toutes les deux vraies, soit toutes les deux fausses.

Nouveau!!: Isomorphisme de graphes et Équivalence logique · Voir plus »

Bijection

En mathématiques, une bijection ou application bijective (parfois appelée correspondances biunivoques) est une application qui est à la fois injective et surjective, autrement dit pour laquelle tout élément de son ensemble d'arrivée possède un et un seul antécédentC'est-à-dire est image d'exactement un élément de son domaine de définition.

Nouveau!!: Isomorphisme de graphes et Bijection · Voir plus »

Bijection réciproque

En mathématiques, la bijection réciproque (ou fonction réciproque ou réciproque) d'une bijection f est l'application qui associe à chaque élément de l'ensemble d'arrivée son unique antécédent par f. Elle se note f^.

Nouveau!!: Isomorphisme de graphes et Bijection réciproque · Voir plus »

Complexité en temps

En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée.

Nouveau!!: Isomorphisme de graphes et Complexité en temps · Voir plus »

Cycle (théorie des graphes)

Dans ce graphe, le cycle rouge est élémentaire. Le cycle bleu ne l'est pas. La chaine verte n'est pas fermée et ne forme donc pas un cycle. Dans un graphe non orienté, un cycle est une suite d'arêtes consécutives distinctes (chaine simple) dont les deux sommets extrémités sont identiques.

Nouveau!!: Isomorphisme de graphes et Cycle (théorie des graphes) · Voir plus »

Graphe griffe

Le graphe griffe est, en théorie des graphes, un graphe possédant 4 sommets et 3 arêtes.

Nouveau!!: Isomorphisme de graphes et Graphe griffe · Voir plus »

Graphe orienté

Un graphe orienté G.

Nouveau!!: Isomorphisme de graphes et Graphe orienté · Voir plus »

Graphe triangle

Le graphe triangle est, en théorie des graphes, un graphe possédant 3 sommets et 3 arêtes.

Nouveau!!: Isomorphisme de graphes et Graphe triangle · Voir plus »

Hassler Whitney

Hassler Whitney (–) est un mathématicien américain et un des fondateurs de la théorie des singularités.

Nouveau!!: Isomorphisme de graphes et Hassler Whitney · Voir plus »

Hypergraphe

Les hypergraphes sont des objets mathématiques généralisant la notion de graphe.

Nouveau!!: Isomorphisme de graphes et Hypergraphe · Voir plus »

Isomorphisme

En mathématiques, un isomorphisme entre deux ensembles structurés est une application bijective qui préserve la structure, et dont la réciproque préserve aussi la structureSi, pour beaucoup de structures en algèbre, cette seconde condition est automatiquement remplie, ce n'est pas le cas en topologie par exemple où une bijection peut être continue sans que sa réciproque le soit.

Nouveau!!: Isomorphisme de graphes et Isomorphisme · Voir plus »

Line graph

En théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960.

Nouveau!!: Isomorphisme de graphes et Line graph · Voir plus »

Mathématiques

Les mathématiques (ou la mathématique) sont un ensemble de connaissances abstraites résultant de raisonnements logiques appliqués à des objets divers tels que les ensembles mathématiques, les nombres, les formes, les structures, les transformations; ainsi qu'aux relations et opérations mathématiques qui existent entre ces objets.

Nouveau!!: Isomorphisme de graphes et Mathématiques · Voir plus »

Morphisme de graphes

Un morphisme de graphes ou homomorphisme de graphes est une application entre deux graphes (orientés ou non orientés) qui respecte la structure de ces graphes.

Nouveau!!: Isomorphisme de graphes et Morphisme de graphes · Voir plus »

NP (complexité)

La classe NP est une classe très importante de la théorie de la complexité.

Nouveau!!: Isomorphisme de graphes et NP (complexité) · Voir plus »

Problème de l'isomorphisme de graphes

Le problème est de savoir si deux graphes sont les mêmes. En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets.

Nouveau!!: Isomorphisme de graphes et Problème de l'isomorphisme de graphes · Voir plus »

Problème NP-complet

En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes.

Nouveau!!: Isomorphisme de graphes et Problème NP-complet · Voir plus »

Relation d'équivalence

En mathématiques, une relation d'équivalence permet, dans un ensemble, de mettre en relation des éléments qui sont similaires par une certaine propriété.

Nouveau!!: Isomorphisme de graphes et Relation d'équivalence · Voir plus »

Structure de données

En informatique, une structure de données est une manière d'organiser les données pour les traiter plus facilement.

Nouveau!!: Isomorphisme de graphes et Structure de données · Voir plus »

Théorie de la complexité (informatique théorique)

P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée…) requis par un algorithme pour résoudre un problème algorithmique.

Nouveau!!: Isomorphisme de graphes et Théorie de la complexité (informatique théorique) · Voir plus »

Théorie des graphes

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.

Nouveau!!: Isomorphisme de graphes et Théorie des graphes · Voir plus »

Tracé de graphes

En théorie des graphes, le tracé de graphes consiste à représenter des graphes dans le plan.

Nouveau!!: Isomorphisme de graphes et Tracé de graphes · Voir plus »

SortantEntrants
Hey! Nous sommes sur Facebook maintenant! »