🎡

# Discrete mathematics

Tags Math @January 6, 2021 3:39 PM @July 4, 2022 7:43 PM

# What is discrete mathematics?

It also known as Mathematics for computer science.

Discrete mathematics is the study of numerable sets, it distinct from others. – such as integers, graphs, and statements in logic.
• Numerable. From Latin numerābilis.
• (mathematics) In one to one correspondence with the set of natural integers.

Collins Dictionary

Wiki

https://www.merriam-webster.com/dictionary/numerable

https://www.dictionary.com/browse/numerable?s=t

Discrete. "separate, distinct from others," late 14c., from Old French discret, discre, and directly from Latin discretus "separated;" see discreet. Related: Discretely; discreteness. https://www.etymonline.com/word/discrete

# Resources

#### The Canon

NameWhy?TopicsAuthorsLast edition
Discrete mathematicsMost topics. Several examples. Coding.Richard Johnsonbaugh
Mathematics for Computer Science - TextbookThe clearestAlbert R MeyerEric LehmanF Thomson Leighton
Discrete Mathematics and Its ApplicationsKenneth H. Rosen
Discrete and combinatorial mathematicasRalph P. Grimaldi
Mathematics for Computer Science (6.042J) - CourseAdam ChlipalaAlbert Meyer
Concrete Mathematics (Second edition)AdvanceDiscrete calculusDiscrete probabilityNumber TheoryDonald E. KnuthOren PatashnikRonald L. Graham

# Requisites

• Minimum formal math.

# Unrequisites

• Calculus
• Coding skills

# Foundations topics

• Set theory
• Sets
• Mathematical logic
• Combinatorics
• Combinations
• Permutations
• Partitions
• Graph theory

Graphs

Networks

• Number theory
• Integers
• Transcendental numbers
• Diophantine approximation
• Function fields
• Algebraic structures
• Boolean algebra
• Relational algebra
• Algebraic coding theory
• Formal languages
• Discretization
• Numerical analysis

# Applications

• Discrete calculus
• Sequences
• Recurrence relation
• Discrete probability
• Discrete geometry
• Discrete collections
• Operations research
• Linear programming
• Optimization
• Queuing theory
• Scheduling theory
• Network theory
• Continous-time Markov process

• Game theory
• Decision theory
• Utility theory
• Social choice theory
• Game theory
• Topology
• Combinatorial topology
• Topological graph theory
• Information theory
• Coding theory
• Analog coding
• Analog signals
• Analog encryption
• Theoretical computer science
• Automata theory
• Formal languages
• Computational geometry

# Sets

## Definitions

### Level 1.

Collection. A group of objects of one type that have been collected by one person or in one place. Oxford dictionary.

Object. The objects are sometimes referred to as elements or members. Elements are unique.

### Level 2.

Group. A number of people or things that are located close together or are considered or classed together. Oxford dictionary.

### Level 3.

Number - The content of a statement of number is an assertion about a concept. [source: The Foundations of Arithmetic, §55, Engl.transl. page 67].

## How to use sets?

$\text{TAG is the set of all elements such that element checks properties}$﻿.

Finite sets. E.g. $A=\{\text{1,2,3,4}\}$﻿

Either infinite or large finite sets. E.g. $A=\{x|x\text{ is positive, even integer} \}$﻿

## Worked examples

• Show that $A=\{1\}\times \{1,2\}\subseteq B=\{1\}\times\{1,2,3\}$﻿

By def. $A\subseteq B \text{ iff } \forall x.x\in A \implies x \in B$﻿

By inspection

$A=\{(1,1),(1,2)\}$﻿, $B=\{(1,1),(1,2),(1,3)\}$﻿

$A\subseteq B$﻿ since every element of $A$﻿ is an element of $B$﻿.

• Show that $A=\{2n|n\in Z^+\}\subseteq B=\{n|n\in Z\}$﻿

By def. $A\subseteq B \text{ iff } \forall x.x\in A \implies x \in B$﻿

Let $x\in A$﻿, $x\in Z^+$﻿ because $Z^+$﻿ is closed under the operation of multiplication. $x\in Z$﻿ since $Z^+\subseteq Z$﻿ .

• Show that $A=\{1,2,3\}\nsubseteq B=\{\}$﻿

By def. $A\subseteq B \text{ iff } \forall x.x\in A \implies x \in B$﻿

but $\{\}$﻿ iff $\forall x.x \notin \{\}$﻿, so the consequent always is $False$﻿, hence $A\nsubseteq B$﻿.

• Show that $A=\{1,2,3,4\}\nsubseteq B=\{n|n\in A \land n+m=8 \text{ for some } m\in C\}$﻿, $C=\{5,6,7,8\}$﻿

By def. $A\subseteq B \text{ iff } \forall x.x\in A \implies x \in B$﻿

$1\in A \implies 1\notin B$﻿, so $A\nsubseteq B$﻿.

• In a group of students, each student is taking a mathematics course or a computer science course or both. One-fifth of those taking a mathematics course are also taking a computer science course, and one-eighth of those taking a computer science course are also taking a mathematics course. Are more than one-third of the students taking a mathematics course?

$C:\text{computer science students}$﻿, $M:\text{mathematics course students}$﻿

We know $\dfrac{|C\cap M|}{|C|}=\dfrac{1}{5}$﻿, $\dfrac{|C\cap M|}{|M|}=\dfrac{1}{8}$﻿ (1), but

$|U|=|C\cup M|=|C|+|M|-|C\cap M|$﻿

$1=\dfrac{|C|}{|U|}+\dfrac{|M|}{|U|}-\dfrac{|C\cap M|}{|U|}$﻿ (2)

By 1

$\dfrac{1}{5}|C|=\dfrac{1}{8}|M|$﻿

$|C|=\dfrac{5}{8}|M|$﻿

We’ll substitute in (2)

$1=\dfrac{5|M|/8}{|U|}+\dfrac{|M|}{|U|}-\dfrac{|M|/8}{|U|}$﻿

$1=\dfrac{12|M|/8}{|U|}$﻿

$\dfrac{|M|}{|U|}=\dfrac{8}{12}=\dfrac{2}{3}\ge\dfrac{1}{3}$﻿

• Let C be a circle and let D be the set of all diameters of C. What is ∩ D? (Here, by “diameter” we mean a line segment through the center of the circle with its endpoints on the circumference of the circle.)

If

$D=\{\{p_{11},p_{12},p_{13},...,Center,...\},\{p_{21},p_{22},p_{23},...,Center,...\},\{p_{31},p_{32},p_{33},...,Center,...\},...\}$﻿

then

$\cap D=\{Center\}$﻿

• Let P denote the set of integers greater than 1 ($P=\{x|x\in Z\land x>1\}$﻿). For i ≥ 2, define $X_i=\{ik|k\in P\}$﻿. Describe $P-\bigcup_{i=2}^\infty X_i$﻿.

$\bigcup_{i=2}^\infty X_i$﻿ describes composite numbers since $X_i$﻿ describes $i$﻿ multiples, so

$=P-\text{composite numbers}=\{x|(x\in Z \land x>1)\land x\notin\text{composite numbers} \}\\ =\text{prime numbers}$﻿

# Mathematical logic

## Key ideas

Logic is the basis of all reasoning.
A statement or proposition is a declarative sentence that is either true or false, but not both. Remember structure no content.
• Don't use "preposition" as synonymous with "statement". A preposition is a word such as 'by', 'for', 'into', or 'with' which usually has a noun group as its object. Collins.
• Other views of propositions. A proposition is the meaning expressed by statements.

A predicate can be understood as a proposition whose truth depends on the value of one or more variables.

## Truth tables

See "truth"

Truth table generator

When you wish to provide a conclusion (or proof in mathematics), you must use chain statements throughout logical consequences (or connectives, methods, and pieces of evidence) from a base set of previous results – such as axioms, theorems, and definitions.

value judgment

• The following statements are primitive prepositions
• Cogito.
• Sum.
• $2+3=5$﻿
• $1+1=3$﻿
• P=NP This is either true or false (but not both), but you don't know.
• for all $x\in R$﻿, $x>0$﻿ then $x^2>0$﻿
• Sun leaves tomorrow.
• She loves him.

• Moreover, the definition does exclude statements such as
• Read 'Cogito ergo sum' in Discourse on the Method. (command)
• Let's go to the beach tomorrow. (proposal)
• $2+3=5?$﻿ (question)
• $P(x):=x+4=6$﻿ (indeterminate declarative sentence). It's a predicate.
• if $x>0$﻿, then $x^2>0$﻿
• $f(x)=x^2$﻿ (indeterminate declarative sentence)
• This sentence is false. Contradictions are not statements. (indeterminate statement).

You gonna use variables to represent prepositions, thus as you use letters in algebra. e.g.

# Logical formulas

## Worked examples

1=-1?

Pythagorean theorem

• Every polynomial ax^2+bx+c has two roots over C.

# Proofs

## What is the proof?

Proof. A finite sequence of statements (called well-formed formulas in the case of a formal language), each of which is a previous result -axiom, an assumption, experiments, or theorems- in the sequence by a rule of inference.

Axiom. Simple postulate or assumption based on a priori knowledge and free contradictions.

Theorems. Important true statements.

Lemma. Preliminary statements.

Corollary. Statements that follows few logical steps from theorem.

Developing mathematical methods to verify programs and systems remains an active research area.

## Good proofs

• Keep a linear flow.
• A proof is an essay, not a calculation.
• Avoid excessive symbolism.
• Revise and simplify.
• Introduce notation thoughtfully.
• Structure long proofs.
• Be wary of the “obvious.”
• Finish.

## Methods

### Proof by perfect induction o Proof by exhaustion

Proof of a Boolean theorem through perfect induction.

### Simple induction

We know by Modus Ponens:

The principle of induction says

$\forall n P(n+1)$﻿ use $\forall n P(n)$﻿ when $\forall n P(n)\implies \forall n P(n+1)$﻿ but the same to simple $P(n+1)$﻿if always is true then $P(n)$﻿ is always true.

## Worked example.

• $\forall n \text{ }n\in N \text{, } P(n):\sum_{i=0}^{n}i=\dfrac{n(n+1)}{2}$﻿

Therefore

• $\forall n \text{ }n\in N \text{ }n>0 \text{, } P(n):n^3\le n^2$﻿

Because $n^3\ge 0,1\ge1,3n^2\ge2n^2$﻿, $3n\ge2 n$﻿

Our theorem is false since

our argument is always false.

• $\forall n \text{ }n\in N \text{ } \text{, } P(n):\dfrac{d^n}{dx^n}x^k=n!x^{k-n}$﻿

Our argument is valid, but it is always false.

• $\forall n,k, \text{ }n\in N \text{ } \text{, } P(n):\dfrac{d^n}{dx^n}x^k=\dfrac{k!}{(k-n)!}x^{k-n}$﻿

As

Our argument is valid and it happen be always true.

https://web.stanford.edu/~dntse/classes/cs70_fall09/cs70-2_notes3.pdf

https://math.stackexchange.com/questions/2926239/when-we-can-use-mathematical-induction-and-when-we-cant

https://www.purplemath.com/modules/inductn2.htm

# Boolean Algebra

California State University

Proof of a Boolean theorem through perfect induction

# Counting

## Cardinality Rules

### The Bijection Rule

Bijection := one-to-one correspondence

Each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set.

What does it mean to write |A| = n?

It means that there is a bijection f : A → {1, . . . , n}

MIT OpenCourseWare. 2016. 3.3.3 Counting with Bijections: Video. YouTube. Retrieved May 25, 2021 from https://www.youtube.com/watch?v=n0lce1dMAh8‌

### The Bijection Rule or Equinumerosity

Let S and T be two finite sets. If there exists one-to-one correspondence (or bijection) between them, from S to T, if and only if $|S|=|T|$﻿ i.e. S and T have the same number of elements. This is taken as the definition.

https://www.cs.colostate.edu/~cs220/summer19/slides/16_bijection_rule.pdf

### Multiplication Principle or Product Rule

$P_1\times P_2\times ... \times P_n=\{(p_1,p_2,...p_n)|p_1\in P_1,p_2 \in P_2,...,p_n\in P_n\}=\text{all sequences}$﻿ called Cartesian product.

Thus, if $P_1,P_2,\cdots ,P_n$﻿ are finite sets, then

For example, if $A=\{x,y,z\}$﻿ and $B=\{1,2,3\}$﻿

$A\times B=\{(x,1),(x,2),(x,3),(y,1),(y,2),(y,3),(z,1),(z,2),(z,3)\}$﻿

$|A\times B|=|A|\cdot|B|=3 \cdot 3=9$﻿

Key ideas

• When we're counting since cardinality $|A|$﻿ is more important than the set $A=\{a_0,a_1,...,a_n\}$﻿. We will ignore writing it.
• No decision might be part b of the set. When your problem says about optional something. $A=\{a_0,a_1,...,a_n,noA\}$﻿
• If repetitions are allowed, $|A|^{repetitions}$﻿
• If repetitions are not allowed, You'd remove the last used element such that $|A|\cdot(|A|-1)\cdot(|A|-2)...$﻿
• $|U|=|A|+|A^c|$﻿

### Product Rule Worked examples

• How many dinners at Kay’s Quick Lunch (Figure 6.1.1) consist of one appetizer and one beverage?

$|Appetizers|=2$﻿, $|Beverages|=4$﻿

$|Dinners|=2\cdot4=8$﻿

• How many dinners at Kay’s Quick Lunch (Figure 6.1.1) consist of an optional appetizer, one main course, and an optional beverage?

$|Main\text{ } courses|=3$﻿

$|optional \text{ } appetizers|=|appetizers|+|no\text{ }appetizer|=2+1=3$﻿

$|optional \text{ }bevarages|=|bevarages|+|no \text{ }bevarage|=4+1=5$﻿

$|Dinners|=|main\text{ } courses| \cdot |optional \text{ } appetizers| \cdot |optional \text{ }bevarages|=3\cdot3\cdot5=45$﻿

• How many dinners at Kay’s Quick Lunch (Figure 6.1.1) consist of one appetizer, one main course, and an optional beverage?

$|Main\text{ } courses|=3,$﻿$|Appetizers|=2,$﻿ $|Beverages|=5$﻿

$|Dinners|=3\cdot2\cdot5=30$﻿

• A man has eight shirts, four pairs of pants, and five pairs of shoes. How many different outfits are possible?

$Outfit=\{(shirt,pair\text{ } of\text{ }pants,pair\text{ } of\text{ }shoes)|shirt\in Shirts,pair\text{ } of\text{ }pants \in Pairs\text{ } of\text{ }pants,pair\text{ } of\text{ }shoes \in Pair\text{ } of\text{ }shoes\}$﻿

$|Shirts|=8$﻿, $|Pairs\text{ } of\text{ }pants|=4$﻿ and, $|Pairs\text{ } of\text{ }shoes|=8$﻿

$|Outfit|=|Shirts|\cdot|Pairs\text{ } of\text{ }pants|\cdot |Pairs\text{ } of\text{ }shoes|=8\cdot 4\cdot5=160$﻿

• Two dice are rolled, one blue and one red. How many outcomes are possible?

$Outcomes=\{(color,position)|color\in Colors,position\in Positions\}$﻿

$|Colors|=2$﻿, $|Positions|=6$﻿

$|Outcomes|=2\cdot6=12$﻿

• The Braille system of representing characters was developed early in the nineteenth century by Louis Braille. The characters, used by the blind, consist of raised dots. The positions for the dots are selected from two vertical columns of three dots each. At least one raised dot must be present. How many distinct Braille characters are possible?

$|Dot|=|Raised \text{ } dot|+|No \text{ } raised \text{ } dot|=2$﻿

$|Dot|^{n\text{ }dots={columns\times rows}}=2^{6}=64$﻿ are Braille characters possibles.

• The options available on a particular model of a car are five interior colors, six exterior colors, two types of seats, three types of engines, and three types of radios. How many different possibilities are available to the consumer?

$|Possibilities|=|Interior\text{ } colors|\cdot |Exterior\text{ } colors|\cdot|Seats|\cdot|Engines|\cdot|Radios|=5 \cdot 6 \cdot 2 \cdot 3 \cdot 3=540$﻿

• How many different car license plates can be constructed if the licenses contain three letters followed by two digits if repetitions are allowed? if repetitions are not allowed?

$\text{Car license plates}=\{(letter,letter,letter,digit,digit)|letter \in \text{English alphabet},digit \in \text{Decimal numeral system}\}$﻿

$|\text{English alphabet}|=26$﻿

$|\text{Decimal numeral system}|=10$﻿

If repetitions are allowed, then

$\text{Car license plates}=26\cdot26\cdot26\cdot10\cdot10=1757600$﻿

If repetitions are not allowed, then

$\text{Car license plates}=26\cdot25\cdot24\cdot10\cdot9=1404000$﻿

• How many 7-digit phone numbers are possible, assuming that the first digit can’t be a 0 or a 1?

$\text{phone numers}=\{(digit_1,digit_2,digit_3,digit_4,digit_5,digit_6,digit_7)|digit_1\in[2,9],digit_2\in[0,9],...\}$﻿

$|\text{phone numbers}|=8\times10^7=8000000$﻿

• Re-solve the previous problem, except now assume also that the phone number is not allowed to start with 911

$\text{911 phone numers}=\{(digit_1,digit_2,digit_3,digit_4,digit_5,digit_6,digit_7)|digit_1\in[9],digit_2\in[1],digit_3\in[1],digit_4\in[0,9],...\}$﻿

$|\text{no 911 phone numbers}|=|\text{phone numbers}|-|\text{911 phone numbers}|=(8\times10^7)-10^4=7990000$﻿

• Why the number of ways to choose 5 people out of 10 is greater than the number of ways to choose 6 people out of 10?
• Why the number of ways to break 10 people into 2 teams of 5 is less than the number of ways to break 10 people into a team of 6 and a team of 4?
• How many different 3x3 pattern locks are possible?

Exercises 10–12 ask about strings of length 5 formed using the letters ABCDEFG without repetitions.

• 10. How many strings begin with the letter F and end with the letter A?

$String=\{(F,letter,letter,letter,A)|letter_\in \{B,C,D,E,G\} \}$﻿

$|\{F\}|=1,|\{A\}|=1,|\{B,C,D,E,G\}|=5$﻿

$|String|=1\cdot5\cdot4\cdot3\cdot1=60$﻿

• 11. How many strings begin with the letter F and do not end with EB in that order?

$U=\{(F,letter,letter,letter,letter)|letter\in \{A,B,C,D,E,G\}\}$﻿

$|U|=1\cdot6\cdot5\cdot4\cdot3=360$﻿

$Strings_{EB}=\{(F,letter,letter,E,B)|letter\in \{A,C,D,G\}\}$﻿

$|Strings_{EB}|=1\cdot4\cdot3\cdot1\cdot1=12$﻿

$|Strings_{noEB}|=|U|-|Strings_{EB}|=348$﻿

• 12. How many strings contain CEG together in that order?

$Strings_0=\{(C,E,G,letter,letter)|letter\in \{A,B,D,F\}\}$﻿

$|Strings_0|=1\cdot1\cdot1\cdot4\cdot3=12$﻿

$Strings_1=\{(letter,C,E,G,letter)|letter\in \{A,B,D,F\}\}$﻿

$|Strings_1|=12$﻿

$Strings_2=\{(letter,letter,C,E,G)|letter\in \{A,B,D,F\}\}$﻿

$|Strings_2|=12$﻿

$|Strings|=|Strings_0|+|Strings_1|+|Strings_2|=36$﻿

But, a sequence n and sub-sequence r together can simplify as $n-r+1$﻿.

$CEG$﻿ sub-sequence, $|\{C,E,G\}|=3$﻿

$(letter,letter,letter,letter,letter),|sequence|=5$﻿, where CEG can be 3 distinct positions.

But, We'll convert to $5-3+1=3$﻿ size sequence, such that

$CEG$﻿ sub-sequence, $|\{CEG\}|=1$﻿

$(letter,letter,letter),|sequence|=3$﻿, where CEG can be 3 distinct positions.

Thus, $|Strings|=((n-r)+1)|String_{CEG}|=36$﻿

Two chess players, A and B, are going to play 7 games. Each game has three possible outcomes: a win for A (which is a loss for B), a draw (tie), and a loss for A (which is a win for B). A win is worth 1 point, a draw is worth 0.5 points, and a loss is worth 0 points.

• How many possible outcomes for the individual games are there, such that overall player A ends up with 3 wins, 2 draws, and 2 losses?

$A=\{(win_1,win_2,win_3,draw_1,draw_2,loss_1,loss_2),...\}$﻿

$|A|={7\choose 3}{4\choose 2}{2\choose 2}=210$﻿

• How many possible outcomes for the individual games are there, such that A ends up with 4 points and B ends up with 3 points?

$A_1=\{(win_1,win_2,win_3,win_4,loss_1,loss_2,loss_3),...\}$﻿

$A_2=\{(win_1,win_2,win_3,draw_1,draw_2,loss_1,loss_2),...\}$﻿

$A_3=\{(win_1,win_2,draw_1,draw_2,draw_3,draw_4,loss_1),...\}$﻿

$A_4=\{(win_1,draw_1,draw_2,draw_3,draw_4,draw_5,draw_6),...\}$﻿

$|\text{All outcomes where A wins by a score of 4}|=|A_1|+|A_2|+|A_3|+|A_4|={7\choose4}+{7\choose3}{4\choose2}+{7\choose2}{5\choose4}+{7\choose1}=357$﻿

• Now assume that they are playing a best-of-7 match, where the match will end when either player has 4 points or when 7 games have been played, whichever is first. For example, if after 6 games the score is 4 to 2 in favor of A, then A wins the match and they don't play a 7th game. How many possible outcomes for the individual games are there, such that the match lasts for 7 games and A wins by a score of 4 to 3?

267

### Addition Principle or Sum Rule

If $A_1,A_2,...,A_n$﻿ are disjoint sets, then:

$|A_1\cup A_1\cup ...\cup A_n|=|A_1|+|A_2|+...+|A_n|$﻿

### Inclusion–exclusion principle

If $X$﻿ and $Y$﻿ are finite sets, then

### The k-to-1 rule or division rule

If B is a finite set and f : A → B maps precisely k items of A to every item of B, then A has k times as many items as B.

The division rule is a common way to ignore “unimportant” differences when you are counting things. You can count distinct objects, and then use the division rule to “merge” the ones that are not significantly different.

### Permutations

A permutation of n things taken r at a time, written P(n,r), is an arrangement in a row of r things, taken from a set of n distinct things. Order matters.

In your problem, $(a_0,a_1,a_2)\ne(a_1,a_2,a_0)?$﻿

Example: How many permutations of the letters ABCDEF contain the letters DEF together in anyorder?

### Counting Subsets or combinations

A combination of n things taken r at a time, written C(n,r) or n r (“n choose r”) is any subset of r things from n things. Order makes no difference.

In your problem, $(a_0,a_1,a_2)=(a_1,a_2,a_0)?$﻿

The key points to remember in this section are that a permutation takes order into account and a combination does not take order into account. Thus, a key to solving counting problems is to determine whether we are counting ordered or unordered items.

Combinatorial Proofs

$n{n-1 \choose k-1}=k{n \choose k}$﻿

Vandermonde's identity

${m+n \choose k} = \sum^k_{j=0} {m \choose j}{n\choose k-j}$﻿

The Binomial Theorem

Pascal’s Triangle Identity

### Worked examples

• How many ways are there to split a dozen people into 3 teams, where one team has 2 people, and the other two teams have 5 people each?

For example, $(x_1,x_2)=(x_2,x_1)$﻿ or $(y_1,y_2,y_3,y_4,y_5)=(z_1,z_2,z_3,z_4,z_5)$﻿. First one references to itself, the second one references to teams by that group by 2.

• How many ways are there to split a dozen people into 3 teams, where each team has 4 people?

$teams=\{((x_1,x_2,x_3,x_4),(y_1,y_2,y_3,y_4),(z_1,z_2,z_3,z_4))|x_1\in[1,12],x_2\in[1,11],...,y_1\in[1,8],...,z_1\in[1,4],...,z_4\in[1],\text{but order doesn't matter}\}$﻿

For example$(y_1,y_2,y_3,y_4)=(z_1,z_2,z_3,z_4)$﻿. First one eferences to teams by that group by 3.

# Finite calculus

## Note

https://web.math.utk.edu/~cplaut/docs/analysis.pdf

http://mitran-lab.amath.unc.edu/courses/MATH564/biblio/text/02.pdf

https://oeis.org/

http://math.colga

An Introduction to Difference Equations (Undergraduate Texts in Mathematics)

Introduction to Difference Equations 978-0486650845

https://www.cimt.org.uk/projects/mepres/alevel/discrete_ch14.pdf

https://www.rand.org/content/dam/rand/pubs/reports/2006/R374.pdf

https://people.math.umass.edu/~lr7q/ps_files/teaching/math456/Chapter3.pdf

# Graph theory

## Definiciones

### Grafo o red -Graph-

$G = (V, E)$﻿, donde V son los vértices y E las aristas.

### Loop

Una arista conectada a un vértice a sí misma.

## Definiciones

 Concepto Def. Ejemplo Representación Observaciones Graph, Network G = (V, E), donde V son los vertices y E las aristas. Loop Una arista conectada a un vertice a si mismo. Directed Cada arista tiene una direccion. Walk Una sequencia @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$v_0v_1v_2...$﻿ Cycle Circuit Open walk Walk donde el primer y el ultimo vertice son distintos. Closed walk Walk donde el primer y el ultimo vertice son iguales. Trail Un walk abierto con distintas aristas. Path Un walk abierto con distintos vertices y aristas. Todos los path son trials. Euler Trail Un trial que incluye todas las aristas del grafo, esto es, en el trial cada arista aparece exactamente una sola vez. Connected Un grafo donde existe un path entre cualquier par de de vertices. Tour Closed Walk que incluye todos las aristas al menos una vez. Euler Tour o Eulerian Circuit Tour donde cada arista es incluida una unica vez. Asi, es un Euler Trial cerrado. Otra def: Un tour de Euler de un grafo dirigido fuertemente conectado G = (V, E) es un ciclo que atraviesa cada arista de G exactamente una vez, aunque podría visitar los vértices en más de una ocasión. Eulerian Eulerian es un grafo que tiene un Euler Tour Component Un maximo conectado subgrafo. Tree Un conectado subgrafo. Free tree Un arbol con ninguna raiz. DAG Grafo aciclico dirigido. Eulerian -Tour de Euler, ciclo euleriano, camino de Euler- Un tour de Euler de un grafo dirigido fuertemente conectado G = (V, E) es un ciclo que atraviesa cada arista de G exactamente una vez, aunque podría visitar los vértices en más de una ocasión. Hamiltonian Grafo con un ciclo visitando cada vertice una vez. Cut -corte- Conjunto de vertices donde cada remoción incrementa el numero de componentes. Cut-set El minimo corte. Cut-edge El tamano de un corte. k-Connected Un grafo conectado con la remoción de k-1 vertices. k-Tough @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$\forall S\subseteq V,S\neq\emptyset$﻿ we have @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$kc(G-S)\le|S|$﻿ k-Regular Un grafo donde todos los vertices tienen grado k. k-Factor Un k-regular esparza un subgrafo. Matching Un conjunto de aristas, no pares que no tienen adjuntos. Clique Un conjunto de vertices que son todos adjuntos. Ind. set Un conjunto de vertices donde ninguno es adjunto. Vertex cover Un conjunto de vertices el cual cubre todos las aristas. Planar graph Un grafo el cual esta embebido en un plano. Plane graph El embemiento de un planar graph. Order Numero de vertices en el grafo. Size Numero de aristas en el grafo.

## Notación

 Español Rep. matemática Ejemplo Grafo o red @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$G$﻿ Nodo o vértice -vertex- @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$v,u$﻿ Conjunto de aristas, arcos o enlace -edge- @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$E(G)$﻿, @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$G.E$﻿ Conjunto de vértices @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$V(G)$﻿, @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$G.V$﻿ Cantidad de componentes @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$c(G)$﻿ Subgrafo inducido @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$G[S]$﻿ Grado de un vértice @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$deg(v)$﻿ Máximo grado del grafo @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$\Delta(G)$﻿ Menor grado del grafo @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$\delta(G)$﻿ Número cromático @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$X(G)$﻿ Número cromático de aristas @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$X_E(G)$﻿ Complemento del grafo @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$G^C$﻿ Grafo completo @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$K_n$﻿ Grafo completo bipartito @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$K_{n,n_2}$﻿ Número de Ramsey @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$r(k,l)$﻿ Grado de entrada @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$in-degree(v)$﻿ Grado de salida @import url('https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.2/katex.min.css')$out-degree(v)$﻿

## Notas

http://www.uop.edu.pk/ocontents/Euler Tours.pdf

https://d3gt.com/unit.html

If you want to represent a graph use Graphviz and its dot language.

Para representar grafos usa Graphviz y su dot languaje, una version online esta disponible o https://edotor.net/

Frank Harary. Graph Theory. Addison-Wesley, 1969.