Formulas and Points

Question 1

List out 2 table header for Adjacency List - Undirected Graph

Answer 1

1. Vertex
2. Adjacent Vertices

Question 2

List out 2 table header for Adjacency List - Directed Graph

Answer 2

1. Initial Vertex
2. Terminal Vertices

• Important
• Write for Out-Degree only

Question 3

List out what must write in Proof by Contrapositive

Answer 3

1. Because the negation of the conclusion of the conditional statement implies that the hypothesis is false, the original conditional statement is true.

Question 4

List out in degree and out degree

Answer 4

1. deg ⁻(V) In-Degree
2. deg ⁺(V) Out-Degree

Question 5

What is the Formula for Handshaking Theorem?

Answer 5

⋿ deg (v) = 2e
v ⋴ V

Question 6

How is loop counted as with degree?
1. Undirected Graph
2. Directed Graph

Answer 6

1. 2
2. 1 In Degree , 1 Out Degree

Question 7

What is the rules for Euler Circuit?

Answer 7

1. All Degree must be Even

• All Vertices at least once
• All Edges exactly once
• Start and End at the same Vertex

Question 8

What is the rules for Euler Path?

Answer 8

1. Exactly 2 Degree must be Odd

• All Vertices at least once
• All Edges exactly once

Question 9

What is the rules for Hamilton Circuit?

Answer 9

1. Need to have Subgraph

• All Vertices exactly once
• Some Edges exactly once
• Start and End at the same Vertex

Question 10

What is the rules for Hamilton Path

Answer 10

1. No special rule

• All Vertices exactly once
• Some Edges exactly once

Question 11

What is the rule for Subgraph?

Answer 11

1. All Vertices are Connected
2. Number of Vertices = Number of Edges
3. Every Vertices has 2 Degree

Question 12

When Hamilton Circult doesn’t exist?

Answer 12

1. There has articulation vertex

a          b
   \       /
        c
    /      \ 
  d         e 

• Here, c is articulation vertex

Question 13

What is the number of chromatic numbers for planar graph?

Answer 13

1. Less than or equal to 4

• Questions can have scheduling questions ( Schedule for Meetings / Final Exams )

Question 14

List out the rules for Trees Diagram

Answer 14

1. All vertices must be connected
2. Don’t have Simple Circuit

a -- c -- d
|   / 
| / 
b 

Simple Circuit
a, b , c , a

/

Question 15

List out the formula for Proof by Contradiction

Answer 15

1. ~ ( p → q ) ≡ p ^ ~q

• We just need to ensure the q negates

Question 16

List out the formula for Proof by Contrapositive

Answer 16

1. p → q ≡ ~q → ~p

• We need to ensure that we assume ** q and p is negate**

Question 17

What is internal vertices?

Answer 17

1. Vertices with children

Question 18

What is leaves?

Answer 18

1. Vertices without children

Question 19

What is decendants and ancestor?

Answer 19

1. Decendants
   
   • All below the current vertices
2. Ancestor
   
   • All above the current vertices

Question 20

How to know the height of the tree diagram?

Answer 20

1. Count the level of the diagram

• Count each level for each layer

     a
    /   \
   b   c

This example has height 1 ( Level 0 and 1 )

• Remember it first starts from level 0

Question 21

Use Following the Wall method to determine
1. Preorder
2. Inorder
3. Postorder

Answer 21

1. Touch the Vertices and Write
2. Touch the Vertices 2nd Time and Write
3. Touch the Vertices Last Time and Write

Question 22

List out the rules for Spanning Tree

Answer 22

1. All vertices ( n ) must be connected with ( n - 1 ) edges
2. Cannot have simple graph inside the spanning tree

• Questions Asked
  1. Road Problem ( Covered with Snow )
  2. IP Multicasting

Question 23

How can I know if the questions wants I use 0 and 1 in Truth Table?

Answer 23

1. If boolean expression is given ( AB + C’ , Q2)

Question 24

How can I know if the questions wants I use T and F in Truth Table?

Answer 24

1. If logic expression is given ( p v ~q , Q1)

Question 25

Try to do this Negation 1. Will 2. And 3. > 250 4. <= 250

Answer 25

1. Will not 2. Or 3. <= 250 4. > 250

Question 26

List out 3 logical equivalant statement

Answer 26

1. Tautology - All True 2. Contradiction - All False 3. Contigency / Indeterminant - Some True / False

Question 27

Can we use [] when representing Logic Gates?

Answer 27

1. Yes

Question 28

How to calculate SOP ( Minterm )

Answer 28

1. All about 1 , X' / A' when 0 in Truth Table xyz + xyz' + x'y'z * Remember write **ABC** when the Truth Table is **ABC**

Question 29

How to calculate POS ( Maxterm )

Answer 29

1. All about 0, X' / A' when 1 in Truth Table ( x' + y + z )( x' + y + z ) ( x' + y' + z ) * Remember write **ABC** when the Truth Table is **ABC**

Question 30

What is Karnaugh Map being used for?

Answer 30

1. Calculate the Simplified SOP ( Minterm )

Question 31

What is Vertex of degree 0 called?

Answer 31

1. Isolation

Question 32

Why does a loop counted as 2 for directed graph and undirected graph?

Answer 32

1. It has 1 in degree and 1 out degree

Question 33

List out the adjacent vertices of vertex c ``` a ← c → b ↙ ↘ d e ```

Answer 33

1. a , b , c , d , e