Dans ce mémoire, nous utiliserons l’approche de Pólya pour dénombrer et énumérer des graphes répondant à certaines conditions. Nous étendons ensuite ce résultat pour des graphes plus spécifiques comme des réseaux, et des réseaux de type "feed-forward". Finalement, nous supposons ensuite que deux sommets d’un graphe puissent être connectés ou non, et étant donné une probabilité de connexion donnée, nous étudions, en tant que variables aléatoires, certaines propriétés que l’on aimerait retrouver parmi ces graphes. Le but de ce mémoire est donc d’étendre la portée du théorème de Pólya afin de dénombrer efficacement plusieurs familles de graphes. Le chapitre 1 servira à l’étude de ce théorème, des rappels nécessaires et suffisants de la théorie des groupes jusqu’à la démonstration du théorème de Pólya. Le chapitre 2 nous permettra de voir la flexibilité du résultat primordial développé au chapitre précédent. Finalement, au chapitre 3, nous abordons une approche plus probabiliste du problème d’énumération de graphes. / In this memoir, we use Pólya approach to count and enumerate graphs under a set of conditions. We then extend the reach of this result for some particular types of graphs, namely networks and feed forward networks. Finally, given probabilistic constraints, e.g. two nodes are connected with probability p, we find the probability that a random graph meets those constraints. The objective of this memoir is thus to remind necessary and sufficient notions of group theory in order to state and prove Pólya Enumeration Theorem, an extremely efficient theorem as for counting objects. We then use this result throughout chapter 2 to enumerate many types of graphs. Chapter 3 is where we get more probabilistic.
| Identifer | oai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/66436 |
| Date | 07 December 2020 |
| Creators | Richard, Anthony |
| Contributors | Doyon, Nicolas |
| Source Sets | Université Laval |
| Language | French |
| Detected Language | French |
| Type | mémoire de maîtrise, COAR1_1::Texte::Thèse::Mémoire de maîtrise |
| Format | 1 ressource en ligne (viii, 67 pages), application/pdf |
| Rights | http://purl.org/coar/access_right/c_abf2 |
Page generated in 0.002 seconds