Defi graph

par **amine801** » 12 Fév 2007, 00:07

hello all
Jai déjà pose ce problème dans ce forum mais il na pas eu un grand succès maintenant que je peux mieux lillustrer
Je me permets de le reposer

pour des graphs non oriente avec n somet je recherche
le nombre exacte de graph a un isomorphime pres(c'est a dir sans renomage de sommet)
dans ce cas la
G1:

et G2:

represente le meme graph G3:

par **Furi0u5** » 12 Fév 2007, 02:01

C'est quoi un graph oriente?
C'est quoi un sommet de recherche?
C'est quoi un isomorphime?
Ca fait parti de quel domaine des mathématiques? :doh:
Ca sert à quoi?
Je pourrais comprendre? :we:

J'veux comprendre! :zen:

par **amine801** » 12 Fév 2007, 02:11

Cest de la théorie des graphes qui a plusieurs application surtout dans linformatique ca peut servir à modélise un réseau par exemple ca peut aussi être utilise pour Lordonnancement de tacheect
Petit lien
http://awal.univ-lehavre.fr/gueye/enseignements_fichiers/graphes.pdf

par **Furi0u5** » 12 Fév 2007, 02:56

Merci :++:

par **amine801** » 12 Fév 2007, 14:31

Pour faciliter les choses jai fait une modification on considère des graphes non orientes
A présent les arcs(flèche) dans la figure peuvent être considère comme bidirectionnels avec linexistence dauto arcs(pas de flèche de 1 vers 1 par exemple)
Donc on recherche le nombre de graphes avec une réelle différence topologique

par **Imod** » 12 Fév 2007, 17:11

Bonjour amine801

On pourrait modéliser le problème de la façon suivante

les

sommets . Un graphe orienté est une partie de

( auquel il faut enlever les (x,x) si on interdit les boucles ) Un graphe non orienté est une partie de

. Deux graphes

et

sont isomorphes s'il existe une permutation

de

telle que

( ou

)

( resp

) . Mais le décompte de tous les graphes non isomorphes risque de ne pas être facile d'autant que

peut donner le même graphe ou simplement un graphe isomorphe au graphe initial .

Imod

par **amine801** » 12 Fév 2007, 17:39

En effet Jai déjà essaye de ce cote la mais jarrive pas a trouver une solution
Jai aussi essayer de compare le cardinal pour des graphes normaux si je put dire

pour établir une relation de récurrence ou autre sans aucun succès
pour n=4 pour des graphes normaux ca fait card=64
pour des graphes a un isomorphisme près ca fait card=11
mais cela ne mavance guère

Defi graph

defi graph

Qui est en ligne