What is a Graph? how highly connected is an entity within a network? What is an entity's overall importance in a network ?
INSTRUCTIONS TO CANDIDATES
ANSWER ALL QUESTIONS
What is a Graph?
- A graph is a data structure representing connections between items
- We're storing values with the potential for connections between any or all elements
- Examples of graphs in everyday life:
- Examples in computer science
- Networks
- Social Network diagrams
- Executing a makefile
Social Networks
Using Social Network Analysis, you can answer:
is an entity within a network?
overall importance in a network?
- How central is an entity within a network?
- How does information
flow within a network?
Makefiles
How make Works
- Construct the dependency graph from the target and dependency entries in
the makefile
- Do a topological sort to determine an order in which to construct
- For each target visited, invoke the commands if the target file does not exist or if any dependency file is newer
- Relies on file modification
dates
Set Theory
- A set is any collection of objects, e.g. a set of vertices
- The objects in a set are called the elements of the set
- Repetition and order are not important
- {2, 3, 5} = {5, 2, 3} = {5, 2, 3, 2, 2, 3}
- Sets can be written in predicate form:
- {1, 2, 3, 4} = {x : x is a positive integer less than 5}
- The empty set is {} = 0, all empty sets are equal
Elements and Subsets
- x ∈ A means “x is an element of A”
- x ∈ A means “x is not an element of A”
- A ⊆ B means “A is a subset of B”
- x ⊆ A means “x is not a subset of A”
A is a proper subset of B and we write A ⊂ B
- A ⊆ A for every set A
- Every set is a subset of itself
Subsets
- If A ⊆ B and B ⊆ C then A ⊆ C
- If A ⊆ B and B ⊆ A then A = B
- The empty set is a subset of every set:
∅⊆ A for any A
- The subsets of A ={1, 2, 3} are:
∅,{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
(Sometimes called the powerset of A, P(A) )
Operations on Sets
- Union
- A ∪ B = { x : x ∈ A or x ∈ B }
- Intersection
- A ∩ B = { x : x ∈ A and x ∈ B }
- Universal Set
- All sets under consideration will be subsets of a background set, called the Universal Set, U
- Complement
- A' = { x : x ∈ U and x ∈ A }
Example
- Let:
- U = {a, b, c, d, e, f}
- A = {a, c}
- B = {b, c, f}
- C = {b, d, e, f}
- Then:
- B ∪ C = {b, c, d, e, f}
- A ∩ (B ∪ C) = {c}
- A' = {b, d, e, f}
= C
- A' ∩ (B ∪ C) = C ∩ (B ∪ C) = {b, d, e, f} = C
Attachments:
Expert's Answer
1053 Times Downloaded
Related Questions
. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:
1
Project 1
Introduction - the SeaPort Project series
For this set of projects for the course, we wish to simulate some of the aspects of a number of
. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:
1
Project 2
Introduction - the SeaPort Project series
For this set of projects for the course, we wish to simulate some of the aspects of a number of
