1.2.6: Graphs

Sets, Logic, Computation · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    Read aloud

    How

    Speed: 1×
    Light up
    Highlight

    Symbols: Mulberry Symbols, © 2018–2026 Steve Lee, CC BY-SA 4.0 (licence, the set), the site's own copies.

    From LibreTexts, under CC BY, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    1.2.6: Graphs

    \(\def\Assign#1#2{ { #1^{\Struct{#2}} } }\)
    \(\def\Atom#1#2{ { \mathord{#1}(#2) } }\)
    \(\def\Bin{ {\mathbb{B}} }\)
    \(\def\cardeq#1#2{ { #1 \approx #2 } }\)
    \(\def\cardle#1#2{ { #1 \preceq #2 } }\)
    \(\def\cardless#1#2{ { #1 \prec #2 } }\)
    \(\def\cardneq#1#2{ { #1 \not\approx #2 } }\)
    \(\def\comp#1#2{ { #2 \circ #1 } }\)
    \(\def\concat{ { \;\frown\; } }\)
    \(\def\Cut{ { \text{Cut} } }\)
    \(\def\Discharge#1#2{ { [#1]^#2 } }\)
    \(\def\DischargeRule#1#2{ { \RightLabel{#1}\LeftLabel{\scriptsize{#2} } } }\)
    \(\def\dom#1{ {\operatorname{dom}(#1)} }\)
    \(\def\Domain#1{ {\left| \Struct{#1} \right|} }\)
    \(\def\Elim#1{ { {#1}\mathrm{Elim} } }\)
    \(\newcommand{\Entails}{\vDash}\)
    \(\newcommand{\EntailsN}{\nvDash}\)
    \(\def\eq[#1][#2]{ { #1 = #2 } }\)
    \(\def\eqN[#1][#2]{ { #1 \neq #2 } }\)
    \(\def\equivclass#1#2{ { #1/_{#2} } }\)
    \(\def\equivrep#1#2{ { [#1]_{#2} } }\)
    \(\def\Exchange{ { \text{X} } }\)
    \(\def\False{ { \mathbb{F} } }\)
    \(\def\FalseCl{ { \lfalse_C } }\)
    \(\def\FalseInt{ { \lfalse_I } }\)
    \(\def\fCenter{ { \,\Sequent\, } }\)
    \(\def\fdefined{ { \;\downarrow } }\)
    \(\def\fn#1{ { \operatorname{#1} } }\)
    \(\def\Frm[#1]{ {\operatorname{Frm}(\Lang #1)} }\)
    \(\def\fundefined{ { \;\uparrow } }\)
    \(\def\funimage#1#2{ { #1[#2] } }\)
    \(\def\funrestrictionto#1#2{ { #1 \restriction_{#2} } }\)
    \(\newcommand{\ident}{\equiv}\)
    \(\newcommand{\indcase}[2]{#1 \ident #2\text{:}}\)
    \(\newcommand{\indcaseA}[2]{#1 \text{ is atomic:}}\)
    \(\def\indfrm{ { A } }\)
    \(\def\indfrmp{ { A } }\)
    \(\def\joinrel{\mathrel{\mkern-3mu}}\)
    \(\def\lambd[#1][#2]{\lambda #1 . #2}\)
    \(\def\Lang#1{ { \mathcal{#1} } }\)
    \(\def\LeftR#1{ { {#1}\mathrm{L} } }\)
    \(\def\len#1{ {\operatorname{len}(#1)} }\)
    \(\def\lexists#1#2{ { \exists #1\, #2 } }\)
    \(\def\lfalse{ {\bot} }\)
    \(\def\lforall#1#2{ { \forall#1\, #2 } }\)
    \(\newcommand{\lif}{\rightarrow}\)
    \(\newcommand{\liff}{\leftrightarrow}\)
    \(\def\Log#1{ { \mathbf{#1} } }\)
    \(\def\ltrue{ {\top} }\)
    \(\def\Id#1{ {\operatorname{Id}_#1} }\)
    \(\def\Int{ {\mathbb{Z}} }\)
    \(\def\Intro#1{ { {#1}\mathrm{Intro} } }\)
    \(\def\mModel#1{ { \mathfrak{#1} } }\)
    \(\newcommand{\mSat}[3][{}]{\mModel{#2}{#1}\Vdash{#3}}\)
    \(\newcommand{\mSatN}[3][{}]{\mModel{#2}{#1}\nVdash{#3}}\)
    \(\def\Nat{ {\mathbb{N}} }\)
    \(\def\nicefrac#1#2{ {{}^#1/_#2} }\)
    \(\def\num#1{ { \overline{#1} } }\)
    \(\def\ran#1{ {\operatorname{ran}(#1)} }\)
    \(\newcommand{\Obj}[1]{\mathsf{#1}}\)
    \(\def\Rat{ {\mathbb{Q}} }\)
    \(\def\Real{ {\mathbb{R}} }\)
    \(\def\RightR#1{ { {#1}\mathrm{R} } }\)
    \(\def\Part#1#2{ { \Atom{\Obj P}{#1, #2} } }\)
    \(\def\pto{ { \hspace{0.1 cm}\to\hspace{-0.44 cm}\vcenter{\tiny{\hbox{|}}}\hspace{0.35 cm} } }\)
    \(\def\PosInt{ {\mathbb{Z}^+} }\)
    \(\def\Pow#1{ {\wp(#1)} }\)
    \(\newcommand{\Proves}{\vdash}\)
    \(\newcommand{\ProvesN}{\nvdash}\)
    \(\def\Relbar{\mathrel{=}}\)
    \(\newcommand{\Sat}[3][{}]{\Struct{#2}{#1}\vDash{#3}}\)
    \(\newcommand{\SatN}[3][{}]{\Struct{#2}{#1}\nvDash{#3}}\)
    \(\newcommand{\Sequent}{\Rightarrow}\)
    \(\def\Setabs#1#2{ { \{#1:#2\} } }\)
    \(\newcommand{\sFmla}[2]{#1\,#2}\)
    \(\def\Struct#1{ {#1} }\)
    \(\def\subst#1#2{ { #1/#2 } }\)
    \(\def\Subst#1#2#3{ { #1[\subst{#2}{#3}] } }\)
    \(\def\TMblank{ { 0 } }\)
    \(\newcommand{\TMendtape}{\triangleright}\)
    \(\def\TMleft{ { L } }\)
    \(\def\TMright{ { R } }\)
    \(\def\TMstay{ { N } }\)
    \(\def\TMstroke{ { 1 } }\)
    \(\def\TMtrans#1#2#3{ { #1,#2,#3 } }\)
    \(\def\Trm[#1]{ {\operatorname{Trm}(\Lang #1)} }\)
    \(\def\True{ { \mathbb{T} } }\)
    \(\newcommand{\TRule}[2]{#2#1}\)
    \(\def\tuple#1{ {\langle #1 \rangle} }\)
    \(\newcommand{\Value}[3][\,]{\mathrm{Val}_{#1}^{#3}(#2)}\)
    \(\def\Var{ { \mathrm{Var} } }\)
    \(\newcommand{\varAssign}[3]{#1 \sim_{#3} #2}\)
    \(\def\Weakening{ { \text{W} } }\)

    A graph is a diagram in which points—called “nodes” or “vertices” (plural of “vertex”)—are connected by edges. Graphs are a ubiquitous tool in discrete mathematics and in computer science. They are incredibly useful for representing, and visualizing, relationships and structures, from concrete things like networks of various kinds to abstract structures such as the possible outcomes of decisions. There are many different kinds of graphs in the literature which differ, e.g., according to whether the edges are directed or not, have labels or not, whether there can be edges from a node to the same node, multiple edges between the same nodes, etc. Directed graphs have a special connection to relations.

    Definition \(\PageIndex{1}\): Directed graph

    A directed graph \(G = \tuple{V, E}\) is a set of vertices \(V\) and a set of edges \(E \subseteq V^2\).

    According to our definition, a graph just is a set together with a relation on that set. Of course, when talking about graphs, it’s only natural to expect that they are graphically represented: we can draw a graph by connecting two vertices \(v_1\) and \(v_2\) by an arrow iff \(\tuple{v_1, v_2} \in E\). The only difference between a relation by itself and a graph is that a graph specifies the set of vertices, i.e., a graph may have isolated vertices. The important point, however, is that every relation \(R\) on a set \(X\) can be seen as a directed graph \(\tuple{X, R}\), and conversely, a directed graph \(\tuple{V, E}\) can be seen as a relation \(E \subseteq V^2\) with the set \(V\) explicitly specified.

    Example \(\PageIndex{1}\)

    The graph \(\tuple{V, E}\) with \(V = \{1, 2, 3, 4\}\) and \(E = \{\tuple{1,1}, \tuple{1, 2}, \tuple{1, 3}, \tuple{2, 3}\}\) looks like this:

    2.6.1_graph.png

    This is a different graph than \(\tuple{V', E}\) with \(V' = \{1, 2, 3\}\), which looks like this:

    2.6.2_graph.png

    Problem \(\PageIndex{1}\)

    Consider the less-than-or-equal-to relation \(\le\) on the set \(\{1, 2, 3, 4\}\) as a graph and draw the corresponding diagram.


    This page titled 1.2.6: Graphs was last modified on Fri, 08 Mar 2024 05:56:10 GMT and is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .