Graph_theory - Wikiparency

# Graph theory Graph theory is the mathematical study of vertices connected by edges, modeling pairwise relations. It encompasses undirected/directed, weighted, planar, and random graphs; classical problems (paths, coloring, flows, matchings); and modern applications in [[Network_science|networks]], algorithms, chemistry, and social analysis.  ## Microsims (promoted from legacy — three.js first) ### MicroSim spec - **Recommended sim type:** network dynamics - **Microsimmability score:** 82/100 - **Layout:** drawing region (canvas) on top; control region (sliders/buttons) below. ### Parameters (tunable controls) - `Number of nodes` - `Edge probability` - `Layout spread` ### What animates Vertices and edges arrange into a graph whose connectivity changes with edge probability. ### Learning objective Show how nodes and edges define a graph's [[Structure|structure]]. ### MicroSim spec - **Recommended sim type:** network / graph - **Microsimmability score:** 85/100 - **Layout:** drawing region (canvas) on top; control region (sliders/buttons) below. ### Parameters (tunable controls) - `Number of vertices` - `Edge density` - `Layout spread` ### What animates Vertices and edges are drawn and you watch connectivity, degree, and paths change as edges are added. ### Learning objective Introduce graphs as vertices joined by edges and read basic graph properties.   ## Microsims — p5.js ### Graph theory (p5.js) · `V, E` <div class="microsim-player"> <iframe src="https://editor.p5js.org/sciencenibber/full/Q1lzsnapy" width="100%" height="480" frameborder="0" loading="lazy" sandbox="allow-scripts allow-same-origin" title="Graph theory — p5.js microsim"></iframe> </div> *The study of nodes and their connections — the domain over which graph signal processing is defined.* **Open in the editor:** [▶ fork this sketch](https://editor.p5js.org/sciencenibber/sketches/Q1lzsnapy) · movement *IX · Foundations & the rest of the toolbox* · library `p5js` ### Related microsims Live sims on neighbouring articles — 6 of them inside this article's own Wikipedia link tree: - [[Analog_signal]] *(in tree)* - [[Autocorrelation]] *(in tree)* - [[Bifurcation_theory]] *(in tree)* - [[Calculus]] *(in tree)* - [[Chaos_theory]] *(in tree)* - [[Communication_channel]] *(in tree)* *Sim hosted off-article; the article owns the reference, not the runtime (WIKI_RULES §10.4). Placed by `g08_place_microsims.py`.*   ## Images <figure class="wt-gifplate"> <img src="https://commons.wikimedia.org/wiki/Special:FilePath/Kuratowski.gif" alt="Graph Embedding" loading="lazy" decoding="async"> <figcaption><strong>Graph Embedding</strong> — Demonstrate graph embedding and topological transformation.<br> <span class="wt-credit">Wikimedia Commons · <strong>licence pending verification</strong> (run <code>g17_gif_verify.py</code> on a networked lane) · <a href="https://commons.wikimedia.org/wiki/File:Kuratowski.gif">Details</a></span></figcaption> </figure> *Still companion to the 1 live microsim above: the sim is the instrument, the plate is the glance. §15 keeps the player first; this sits in the image slot on [[Graph_theory]].*  ## Reveal %%REVEAL:d3%% %%REVEAL:svg%% --- *Concept aligned with [Wikipedia](https://en.wikipedia.org/wiki/Graph_theory); adapted text, where present, is licensed [CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/).* ## Overview Within [[Mathematics|mathematics]] it anchors [[Discrete_mathematics|discrete mathematics]] and [[Combinatorics|combinatorics]], trading tools with [[Topology|topology]], [[Probability_theory|probability theory]], [[Algebraic_geometry|algebraic geometry]], and [[Category_theory|category theory]]. In [[Computer_science|computer science]] every [[Algorithm|algorithm]] over connectivity, shortest paths, or matching is graph theory at work, and [[Computational_geometry|computational geometry]] and [[Computer_algebra|computer algebra]] lean on the same scaffolding. As the substrate of applied structure it powers [[Social_network_analysis|social network analysis]], [[Statistical_mechanics|statistical-mechanics]] models of connectivity, [[Computational_neuroscience|computational neuroscience]], [[Mathematical_and_theoretical_biology|mathematical biology]], and the optimization stock-in-trade of [[Operations_research|operations research]] and [[Mathematical_optimization|mathematical optimization]] — which is why [[Cybernetics|cybernetics]], [[Information_theory|information theory]], and [[Game_theory|game theory]] all speak fluent graphs.  *Built to the [[WT!P5_js_Microsim_Master_Class|p5.js Master Class]].*  ## Wikipedia : Wikitube **Strict pair:** [Wikipedia](https://en.wikipedia.org/wiki/Graph_theory) : [Wikitube](https://en.wikitube.io/wiki/Graph_theory) ## Previous hub tags Hubs: `Systems`. Portals: [[PORTAL_Systems]], [[PORTAL_Graph_theory]].