# Definition(s) In general a graph is a pair $(V,E)$ where $V$ is any set and $E$ entails connections between elements of $v$: > [!NOTE] Definition (Graph - Undirected Graph without loops) > A **graph** (or **undirected graph**, or **network**) is pair of [[Sets|sets]] $(V,E)$ such that $E \subseteq {V\choose 2}$ (where ${V\choose 2}$ is the set of two element subsets of $V$). > > > **Terminology**: - The elements of $V$ are called its [[Graph vertex|vertices]] (or **nodes**, or **points**) and those of $E$ are called its **edges** which indicate a relationship between two nodes. - The edge $e=\{ u,v \}\in {V \choose 2}$ is also denoted $e=uv.$ - If $e = uv\in E$ then $u$ is called *adjacent* to $v$ and incident to $e.$ - If $e_{1},e_{2}\in E$ then they are adjacent iff $e_{1} \cap e_{2} \neq 0,$ i.e. the two edges are incident to the same vertex in $G.$ **Remarks**: $E$ can be seen as a [[Binary Relation|relation]] on $V$. Allowing edges to be undirected corresponds to [[Symmetric Relation|symmetry]] of this relation. Disallowing loops corresponds to the [[Irreflexive relation|irreflexivness]] of this relation. > [!NOTE] Definition (MultiGraph - Undirected graphs with parallel edges but without loops) > A **multigraph** (or **undirected multigraph**, or **graph**) is a pair $(V,E)$ for some set $V$ such that $E = \{ \{ u_{1},u_{2} \} \mid u_{1}, u_{2} \in V \}$ is a [[Multiset|multiset]]. > > >- Note that the above definitions don't admit self loops since $\{ u, u \}=\{ u \}$ which is clearly not a two element subset so $\{ u,u \} \not \in E$. >- To admit loops we can redefine the edge sets as $E\subseteq {V\choose 1} \cup {V\choose 2}.$ >- A graph is *simple* iff it does not contain loops or parallel edges. > [!NOTE] Definition (DiGraph - Directed graph with self loops) > A **[[Directed Graph|directed graph]]** (or **digraph**) is a pair of sets $(V,E)$ such that $E\subseteq V^{2}.$ > [!NOTE] Definition (MultiDiGraph - Directed graph with loops and parallel edges) > A **directed multigraph** (or **directed graph**) is a pair $(V,E)$ for some set $V$ such that $E = \{ (u_{1},u_{2} ) \mid u_{1}, u_{2} \in V \}$ is a [[Multiset|multiset]]. > # Properties A [[subgraph]] of $G:=(V,E)$ is a graph whose vertex-set and edge-set are subsets of those of $G$. We may assign a weight to each edge $w: E\to \mathbb{R}$. Then $(G,w)$ is known as a [[Weighted Graph|weighted graph]]. See [[Isomorphism of Graphs]]. A graph is given by an [[Adjacency Matrix|adjacency matrix]]. **Graph Traversal**: A [[Walk in Undirected Graph|walk]] is any finite sequence of vertices such that adjacent vertices have an edge between them. A graph is [[Connected Graph|connected]] iff there exists a walk between any two vertices. A graph is [[Complete Graph|complete]] if all its vertices are pairwise adjacent. **Graph Matching**: A [[Matching (in graphs)|matching]] of a graph is a set of independent edges (edges that do not share any nodes in common). A set of vertices of $G$ is a [[Vertex Cover|vertex cover]] iff every edge of $G$ is incident with a vertex in $U.$ A graph is [[Graph Colouring|bipartite]] iff we can partition it vertex-set such that vertices in the same partition do not share any edges. # Examples Using [[NetworkX]] python package to visualise $K_{5}$: ```run-python import networkx as nx import matplotlib.pyplot as plt G = nx.complete_graph(5) nx.draw(G) plt.show() ``` # Applications See [[Clustering in Real World Networks]].