Scribd
Upload
19 views2 pages

ITE 048 Discrete Structures Module Guide

The document provides a comprehensive guide on discrete structures, focusing on key terminologies related to trees and graphs, including definitions of nodes, paths, and cycles. It outlines various types of trees, important graph concepts such as Euler and Hamiltonian cycles, and distinctions between similar and dissimilar graphs. Additionally, it includes sample path analyses and tree identification methods from a graph.

Uploaded by

jamilegonzales00
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views2 pages

ITE 048 Discrete Structures Module Guide

The document provides a comprehensive guide on discrete structures, focusing on key terminologies related to trees and graphs, including definitions of nodes, paths, and cycles. It outlines various types of trees, important graph concepts such as Euler and Hamiltonian cycles, and distinctions between similar and dissimilar graphs. Additionally, it includes sample path analyses and tree identification methods from a graph.

Uploaded by

jamilegonzales00
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

ITE 048 Discrete Structures – Module Guide & Reviewer

I. Key Terminologies

• Ancestor – All nodes along the path from the root to a given node.

• Descendant – All nodes of the sub-trees of a node.

• Root Node – A node with no parents or ancestors.

• Parent – The immediate root of a node.

• Degree of a Node – The number of sub-trees of a node.

• In-degree – The number of edges where the vertex is the head (2nd component).

• Level/Generation of a Node – The depth of a node, calculated as 1 + length of its path from the
root.

• Non-leaf or Non-terminal Nodes – Nodes that have at least one child.

• Weight of a Tree – The number of leaf nodes.

• Backtracking – A technique that systematically explores all paths through the state space until a
goal is found.

II. Types of Trees (Aside from Binary Tree)

1. General Tree

2. N-ary Tree

3. AVL Tree

4. Red-Black Tree

5. B-Tree

6. B+ Tree

7. Trie

8. Splay Tree

III. Graph Theory Concepts

• Path – A sequence of edges connecting a sequence of vertices.

• Simple Path – A path where no vertex is repeated.

• Cycle – A path that starts and ends at the same vertex.

• Simple Cycle – A cycle where no vertex repeats except for the first and last vertex.

Sample Path Analysis

• (1, 2, 3, 4, 5, 6) → Simple Path: Yes | Cycle: No | Simple Cycle: No

• (3, 4, 7, 6, 5, 3) → Simple Path: No | Cycle: Yes | Simple Cycle: Yes

• (5, 3, 1, 2, 3, 4, 5) → Simple Path: No | Cycle: Yes | Simple Cycle: No

• (5, 4, 7, 6, 5) → Simple Path: No | Cycle: Yes | Simple Cycle: Yes

• (3, 4, 7, 6, 4, 5, 3) → Simple Path: No | Cycle: Yes | Simple Cycle: No

IV. Tree Identification from a Graph

• Parent of a Node – The node directly above it in the hierarchy.


• Ancestors of a Node – All nodes from the root to that node.

• Children of a Node – Nodes that directly descend from a given node.

• Descendants of a Node – All nodes under a given node in the tree.

• Siblings – Nodes with the same parent.

• Terminal Vertices (Leaf Nodes) – Nodes with no children.

• Internal Vertices – Nodes that are not leaf nodes.

• Height of a Tree – The longest path from the root to a leaf node.

• Weight of a Tree – The number of leaf nodes.

V. Important Graph Concepts

1. Euler Cycle vs. Hamiltonian Cycle

• Euler Cycle – A cycle that visits every edge exactly once and returns to the starting vertex.

• Hamiltonian Cycle – A cycle that visits every vertex exactly once and returns to the starting
vertex.

2. Similar vs. Dissimilar Graphs

• Similar Graphs – Graphs that have the same structure and connections.

• Dissimilar Graphs – Graphs that differ in structure or connectivity.

3. Binary Search Tree (BST)

• A tree where each node has at most two children.

• The left subtree contains values less than the parent node.

• The right subtree contains values greater than the parent node.

4. Spanning Tree

• A subgraph of a connected graph that includes all vertices with the minimum number of edges.

• No cycles are present in a spanning tree.

You might also like