BZU PAGES: Find Presentations, Reports, Student's Assignments and Daily Discussion; Bahauddin Zakariya University Multan Right Header

Register FAQ Community Calendar New Posts Navbar Right Corner
HOME BZU Mail Box Online Games Radio and TV Cricket All Albums
Go Back   BZU PAGES: Find Presentations, Reports, Student's Assignments and Daily Discussion; Bahauddin Zakariya University Multan > Institute of Computing > Bachelor of Science in Telecom System > BsTS 2nd Semester


Reply
 
Thread Tools Search this Thread Rate Thread Display Modes
  #1  
Old 26-02-2011, 11:55 PM
bonfire's Avatar
M.Arsalan Qureshi

 
Join Date: Oct 2008
Location: Garden Town, Multan Cantt
Posts: 616
Program / Discipline: BSTS
Class Roll Number: 09-31
bonfire has a reputation beyond reputebonfire has a reputation beyond reputebonfire has a reputation beyond reputebonfire has a reputation beyond reputebonfire has a reputation beyond reputebonfire has a reputation beyond reputebonfire has a reputation beyond reputebonfire has a reputation beyond reputebonfire has a reputation beyond reputebonfire has a reputation beyond reputebonfire has a reputation beyond repute
Default Concept of Graph in Data Structures.

What is a graph?

A graph is a way of representing connections between places. Mathematically, a graph is a collection of nodes and edges. Nodes are locations that are connected together by the edges of the graph. For instance, if you had two small towns connected by a two-way road, you could represent this as a graph with two nodes, each node representing a town, and one edge, the road, connecting the two towns together. In addition to the undirected graph, in which the edge is a two-way connection, there are directed graphs, in which edges connect only one way. For instance, you could represent the previous example of two cities connected by a road as a directed graph consisting of two nodes and two edges, each edge connecting one of the nodes to the other. In the city example, it may also be convenient to record the distance between the two cities; this can be expressed by adding a 'weight' to an edge, which is a number that usually corresponds to the distance covered by an edge (the distance between two nodes).

Why are graphs useful?

Computer scientists have developed a great deal of theory about graphs and operations on them. One reason for this is because graphs can be used to represent many problems in computer science that are otherwise abstract. Finding a way to represent the solution to a problem as a graph can present new approaches to solving the problem or even lead directly to a solution derived from graph theory. This sort of technique is often used when discussing algorithmic efficiency and when trying to prove that a certain algorithm is NP-Complete; because many problems involving graphs, such as finding the shortest path to traverse all nodes (the Traveling Salesman Problem), are NP-Complete, if you can find a way to represent a problem as a graph and show that it is analogous to one of the other NP-Complete problems, then you can show the problem you are trying to solve is also NP-Complete, which gives you a hint that the solution will take a great deal of time.

Another reason for using graphs is that many problems computers are used to solve involve representing relationships between objects, places, or concepts. Because graphs can be either directed or undirected, they are a flexible method of showing connections. For instance, you can describe who knows whom in a room as a collection of nodes, each representing a person, and directed edges, each representing that one person knows another.

Because graphs are so often used and because they allow the representation of many problems in computer science, such as the Traveling Salesman Problem or something as simple as the relationships between people in a room, they are a convenient means of expressing problems with which many people are comfortable. This familiarity simplifies the process of creating mental models of problems, which ultimately leads to better problem solving.

What are some important graph theory terms?

Directed Graph: A directed graph is one in which edges connect nodes in only one direction.

Undirected Graph: An undirected graph is one in which edges connect nodes bidirectionally (in both directions). Node: A node, usually drawn as a circle, represents an item that can be related to other items or nodes. Nodes are sometimes referred to as vertices.

Edge: An edge represents a connection between nodes. Edges can be either directed or undirected, depending on the type of graph. Edges can also have weights, which may correspond to strength of relationship or distance between edges. (For instance, if a graph represents a map, then the weights of each edge will represent the distance between two nodes.)

Connected: A graph is connected if from any node you can reach any other node.

Disconnected: A graph is disconnected if certain groups of nodes from an island that has no connection to the rest of the graph.
Attached Files
File Type: docx Graph in Data Structure (www.bzupages.com).docx (32.6 KB, 337 views)
__________________

Reply With Quote
Reply

Tags
concept, data, graph, structures


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
Trees in Data Structures bonfire BsTS 2nd Semester 1 04-12-2011 11:29 PM
Heap in Data Structures bonfire BsTS 2nd Semester 0 26-02-2011 11:52 PM
Queue in Data Structures bonfire BsTS 2nd Semester 0 26-02-2011 11:51 PM
Stacks in Data Structures bonfire BsTS 2nd Semester 0 26-02-2011 11:50 PM
[PPT] Chapter 2. Data Warehouse and OLAP Technology for Data Mini - Data Mining Concepts and Techniques Han and Kamber BSIT07-01 Dataware Housing & data mining 0 03-11-2010 03:10 AM

Best view in Firefox
Almuslimeen.info | BZU Multan | Dedicated server hosting
Note: All trademarks and copyrights held by respective owners. We will take action against any copyright violation if it is proved to us.

All times are GMT +5. The time now is 08:03 AM.
Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.