Sriraman Sridharan - Discrete Mathematics: Graph Algorithms, Algebraic Structures, Coding Theory, and Cryptography

Discrete Mathematics

Graph Algorithms, Algebraic Structures, Coding Theory, and Cryptography

Discrete Mathematics

Graph Algorithms, Algebraic Structures, Coding Theory, and Cryptography

R. Balakrishnan

Bharathidasan University, Tiruchirappalli, Tamil Nadu, INDIA

Sriraman Sridharan

Laboratoire LAMPS, Dpartement de Mathmatiques et dInformatique, Universit de Perpignan Via Domitia, Perpignan, FRANCE

CRC Press

Taylor & Francis Group

6000 Broken Sound Parkway NW, Suite 300

Boca Raton, FL 33487-2742

2020 by Taylor & Francis Group, LLC

CRC Press is an imprint of Taylor & Francis Group, an Informa business

No claim to original U.S. Government works

Printed on acid-free paper

International Standard Book Number-13: 978-0-8153-4739-2 (Hardback)

This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers.

For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe.

Library of Congress Cataloging-in-Publication Data

Names: Sridharan, Sriraman, author. | Balakrishnan, R. (Rangaswami), author.

Title: Discrete mathematics : graph algorithms, algebraic structures, coding theory, and cryptography / Sriraman Sridharan, R. Balakrishnan.

Description: Boca Raton : CRC Press, Taylor & Francis Group, 2019. | Includes bibliographical references and index.

Identifiers: LCCN 2019011934| ISBN 9780815347392 (hardback : alk. paper) | ISBN 9780429486326 (ebook)

Subjects: LCSH: Mathematics--Textbooks. | Computer science--Textbooks.

Classification: LCC QA39.3 .S7275 2019 | DDC 511/.1--dc23

LC record available at https://lccn.loc.gov/2019011934

Visit the Taylor & Francis Web site at

http://www.taylorandfrancis.com

and the CRC Press Web site at

http://www.crcpress.com

The first author, R. Balakrishnan, dedicates this book

affectionately to his granddaughters:

Amirtha and Aparna

The second author, Sriraman Sridharan, dedicates this book in

memory of his thesis supervisor:

Professor Claude Berge

Contents

Discrete Mathematics and Programming courses are all-pervasive in Computer Science, Mathematics, and Engineering curricula. This book is intended for undergraduate/graduate students of Computer Science, Mathematics, and Engineering. The book is in continuation of our first book, Foundations of Discrete Mathematics with Algorithms and Programming (CRC Press, 2018). The student with a certain mathematical maturity and who has programmed in a high-level language like C (although C is not such a high-level language) or Pascal can use this book for self-study and reference. A glance at the Table of Contents will reveal that the book deals with fundamental graph algorithms, elements of matrix theory, groups, rings, ideals, vector spaces, finite fields, coding theory, and cryptography. A number of examples have been given to enhance the understanding of concepts. The programming languages used are Pascal and C. The aim of the book is to bring together advanced Discrete Mathematics with Algorithms and Programming for the student community.

Scope of the Book

In on Graph Algorithms I, we study various algorithms on graphs. Unfortunately, the graphs are not manipulated by their geometrical representation inside a computer. We start with two important representations of graphs, the adjacency matrix representation, and the adjacency list representation. Of course, we have to choose a representation so that the operations of our algorithm can be performed in order to minimize the number of elementary operations.

After seeing how the graphs are represented inside a computer, two minimum spanning tree algorithms in a connected simple graph with weights associated with each edge, one due to Prim and the other invented by Kruskal, are presented.

Then, shortest path problems in a weighted directed graph are studied. First, the single-source shortest path problem due to Dijkstra is presented. Next, the single-source shortest path algorithm for negative edge weights is given. Then, the all-pairs shortest path problem due to Floyd and the transitive closure algorithm by Warshall are given. Floyd's algorithm is applied to find the eccentricities of vertices, radius, and diameter of a graph.

Finally, we study a well-known graph traversal technique, called depth-first search. As applications of the graph traversal method, we study the algorithms to find connected components, biconnected components, strongly connected components, topological sort, and PERT (program evaluation and research technique). In the last subsection, we study the famous NP-complete problem, the traveling salesman problem (TSP) and present a brute force algorithm and two approximate algorithms.

In : Graph Algorithms II, we introduce another systematic way of searching a graph, known as breadth-first search. Testing if a given graph is geodetic and finding a bipartition of a bipartite graph are given as applications. Next, matching theory is studied in detail. Berges characterization of a maximum matching using an alternating chain and the Knig-Hall theorem for bipartite graphs are proved. We consider matrices and bipartite graphs: Birkhoff-von-Neumann theorem concerning doubly stochastic matrices is proved. Then, the bipartite matching algorithm using the tree-growing procedure (Hungarian method) is studied. The Kuhn-Munkres algorithm concerning maximum weighted bipartite matching is presented. Flows in transportation networks are studied.

: Algebraic Structures I deals with the basic properties of the fundamental algebraic structures, namely, groups, rings, and fields. The sections on matrices deal with the inverse of a non-singular matrix, Hermitian and skew-Hermitian matrices, as well as orthogonal and unitary matrices. The sections on groups deal with Abelian and non-Abelian groups, subgroups, homomorphisms, and the basic isomorphism theorem for groups. We then pass on to discuss rings, subrings, integral domains, ideals, fields, and their characteristics. A number of illustrative examples are presented.