2.6: Графіки

Last updated
Save as PDF

Page ID: 53143

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Template:MathJaxZach

Графік - це діаграма, на якій точки - звані «вузлами» або «вершинами» (множина «вершини») - з'єднані ребрами. Графіки є всюдисущим інструментом в дискретній математиці та в інформатиці. Вони неймовірно корисні для представлення та візуалізації відносин та структур, від конкретних речей, таких як мережі різного роду, до абстрактних структур, таких як можливі результати рішень. У літературі існує багато різних типів графіків, які відрізняються, наприклад, залежно від того, спрямовані ребра чи ні, мають мітки чи ні, чи можуть бути ребра від вузла до одного вузла, кілька ребер між одними і тими ж вузлами тощо. відносини.

Визначення\(\PageIndex{1}\): Directed graph

\(G = \tuple{V, E}\)ОріЄНТОВАНИЙ ГРАФ - це сукупність вершин\(V\) і набір ребер\(E \subseteq V^2\).

Згідно з нашим визначенням, графік просто є множиною разом із співвідношенням на цій множині. Звичайно, говорячи про графіки, цілком природно очікувати, що вони графічно представлені: ми можемо намалювати графік, з'єднавши дві вершини\(v_1\) і\(v_2\) стрілкою iff\(\tuple{v_1, v_2} \in E\). Єдина відмінність між співвідношенням само по собі і графом полягає в тому, що граф визначає набір вершин, тобто граф може мати ізольовані вершини. Важливим моментом, однак, є те, що кожне відношення\(R\) на множині\(X\) можна розглядати як орієнтований граф\(\tuple{X, R}\), і навпаки, орієнтований граф\(\tuple{V, E}\) можна розглядати як відношення\(E \subseteq V^2\) з множиною \(V\)явно вказано.

Приклад\(\PageIndex{1}\)

Графік\(\tuple{V, E}\) з\(V = \{1, 2, 3, 4\}\) і\(E = \{\tuple{1,1}, \tuple{1, 2}, \tuple{1, 3}, \tuple{2, 3}\}\) виглядає так:

2.6.1_графік.png

Це інший графік, ніж\(\tuple{V', E}\) з\(V' = \{1, 2, 3\}\), який виглядає так:

2.6.2_графік.png

Проблема\(\PageIndex{1}\)

Розглянемо відношення менше або рівно-до\(\le\) на множині\(\{1, 2, 3, 4\}\) як графік і намалюйте відповідну діаграму.